J. Crazy Cattle 2D
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The cows have escaped Farmer John's barn and have run loose! Farmer John's pasture is an $$$n$$$ by $$$m$$$ grid, with an indestructible fence surrounding the pasture.

There are $$$k$$$ cows in the pasture, each moving in a cardinal direction$$$^{\text{∗}}$$$. Every second, the cows instantaneously move to a cell in their respective direction. If multiple cattle occupy the same cell, they all simultaneously explode. Alternatively, if a cow leaves the pasture, it also explodes.

Farmer John is attempting to stage an intervention and needs analytics data. Please help Farmer John determine how long each cow survives!

$$$^{\text{∗}}$$$The four cardinal directions are North, East, South, and West.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10^3$$$). The description of the test cases follows.

The first line of each test case contains integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \leq n \cdot m \leq 1.5 \cdot 10^{5}$$$, $$$1 \leq k \leq n \cdot m$$$) — the number of rows in the grid, the number of columns in the grid, and the number of cows.

The next $$$k$$$ lines contain two integers, $$$r_i$$$ and $$$c_i$$$, and a character $$$d_i$$$ ($$$1 \leq r_i \leq n, 1 \leq c_i \leq m, d_i \in \{\texttt{N}, \texttt{E}, \texttt{S}, \texttt{W}\}$$$) — the row, column, and direction of the $$$i$$$-th cow. The directions are given as a character $$$\texttt{NESW}$$$, indicating its respective cardinal direction. No two cows will start on the same cell.

It is guaranteed that the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$1.5 \cdot 10^5$$$.

—

Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

Tests $$$1-2$$$ satisfies $$$\sum n \cdot m \leq 10^{3}$$$.

Tests $$$3-6$$$ satisfy $$$n = 1$$$.

Tests $$$7-20$$$ satisfy no additional constraints.

Output

For each test case, output the number of seconds each cow survived.

Example
Input
3
2 2 2
1 1 E
1 2 W
2 2 2
1 2 S
2 1 E
1 4 4
1 1 E
1 2 E
1 3 E
1 4 E
Output
2 2
1 1
4 3 2 1
Note

For the first test case:

  • At $$$t=0$$$, cow $$$1$$$ is at $$$(1, 1)$$$, and cow $$$2$$$ is at $$$(1, 2)$$$.
  • At $$$t=1$$$, cow $$$1$$$ is at $$$(1, 2)$$$, and cow $$$2$$$ is at $$$(1, 1)$$$.
  • At $$$t=2$$$, both cows $$$1$$$ and $$$2$$$ exit the grid and explode.

Note that the cows do not collide, since they move instantaneously.

For the second test case:

  • At $$$t=0$$$, cow $$$1$$$ is at $$$(1, 2)$$$, and cow $$$2$$$ is at $$$(2, 1)$$$.
  • At $$$t=1$$$, cow $$$1$$$ is at $$$(2, 2)$$$, and cow $$$2$$$ is at $$$(2, 2)$$$. Since they are in the same cell, they both explode.

—

Problem Idea: alexlikemath007

Problem Preparation: eysbutno

Occurrences: Novice J, Advanced F