Description

Evirir the dragon has yet again laid siege on MCO land. To defend against Evirir's attack, the inhabitants of MCO land have prepared anti-aircraft guns equipped with dragon scale-piercing ammunition.

MCO land can be modeled as an $n$ by $m$ grid with the rows labeled $1$ to $n$ from top to bottom and columns labeled $1$ to $m$ from left to right. The cell in the $i^{\text{th}}$ row, and the $j^{\text{th}}$ column is denoted by $(i,j)$. There is an AA gun in each cell. To better shoot down Evirir the dragon, the guns will follow Evirir the dragon as he flies around MCO land.

Duckmoon, the former president of MCO Land, will issue a series of $T$ commands to the inhabitants, directing them to move guns. These directions are specified in a string $S$ of length $T$, which is composed of the characters $\tt{N}$, $\tt{S}$, $\tt{E}$, and $\tt{W}$. At the $i^{\text{th}}$ command, represented by $S_i$, all the guns in MCO land will move in the following manner:

• If $S_i = \tt{N}$, guns are directed northward. A gun at position $(i,j)$ moves to $(i-1,j)$ if $i > 1$; otherwise, it remains stationary.
• If $S_i = \tt{S}$, guns are directed southward. A gun at position $(i,j)$ moves to $(i+1,j)$ if $i < n$; otherwise, it remains stationary.
• If $S_i = \tt{E}$, guns are directed eastward. A gun at position $(i,j)$ moves to $(i,j+1)$ if $j < m$; otherwise, it remains stationary.
• If $S_i = \tt{W}$, guns are directed westward. A gun at position $(i,j)$ moves to $(i,j-1)$ if $j > 1$; otherwise, it remains stationary.

Note that a cell can have multiple guns at the same time.

After Evirir the dragon is shot down, the inhabitants of MCO land will need to store away the AA guns. For each pair $(i,j)$ with $1 \leq i \leq n$, $1 \leq j \leq m$, the inhabitants of MCO land want to know which cell the gun originally in $(i,j)$ will end up in after all $T$ commands.

An integer is used to describe the final position of each gun. If a gun ends up in cell $(x, y)$, its final position is represented by the integer $(x - 1) \times m + (y - 1)$.

Input Format

The first line consists of three space-separated integers $n,m$ and $T$ denoting the number of rows, number of columns, and number of commands given by Duckmoon respectively. It is guaranteed that $1 \leq n,m,T \leq 10^6$ and $nm \leq 10^6$.

The second line contains a string $S$ of length $T$ consisting of the characters $\tt{N}, \tt{S}, \tt{E}, and \tt{W}$.

Output Format

Let $(x_{i,j},y_{i,j})$ be the cell the gun originally in cell $(i,j)$ ends up in.

Output $n$ lines. For the $i^{\text{th}}$ line, output $m$ space-separated integers $q_{i,1},q_{i,2},...,q_{i_m}$ where $q_{i,j} = (x_{i,j}-1) \times m + (y_{i,j} - 1)$.

3 4 5
NEESW

5 6 6 6
5 6 6 6
9 10 10 10

7 5 20
WSSWNSENSNWENESSNSEW

12 12 12 13 13
17 17 17 18 18
22 22 22 23 23
27 27 27 28 28
32 32 32 33 33
32 32 32 33 33
32 32 32 33 33

Hint

Note

Here is the visualization for Example 1, showing the coordinates of the original AA gun and how they are directed based on the commands.

$$\begin{array}{|c|c|c|c|c|} \hline & \text{Column 1} & \text{Column 2} & \text{Column 3} & \text{Column 4} \\ \hline \text{Row 1} & (1,1) & (1,2) & (1,3) & (1,4) \\ \hline \text{Row 2} & (2,1) & (2,2) & (2,3) & (2,4) \\ \hline \text{Row 3} & (3,1) & (3,2) & (3,3) & (3,4) \\ \hline \end{array}$$

After the command N, they move northward.

$$\begin{array}{|c|c|c|c|c|} \hline & \text{Column 1} & \text{Column 2} & \text{Column 3} & \text{Column 4} \\ \hline \text{Row 1} & (1,1), (2,1) & (1,2), (2,2) & (1,3), (2,3) & (1,4), (2,4) \\ \hline \text{Row 2} & (3,1) & (3,2) & (3,3) & (3,4) \\ \hline \text{Row 3} & & & & \\ \hline \end{array}$$

After the command E, they move eastward.

$$\begin{array}{|c|c|c|c|c|} \hline & \text{Column 1} & \text{Column 2} & \text{Column 3} & \text{Column 4} \\ \hline \text{Row 1} & & (1,1), (2,1) & (1,2), (2,2) & (1,3), (1,4), (2,3), (2,4) \\ \hline \text{Row 2} & & (3,1) & (3,2) & (3,3), (3,4) \\ \hline \text{Row 3} & & & & \\ \hline \end{array}$$

After the command E, they move eastward again.

$$\begin{array}{|c|c|c|c|c|} \hline & \text{Column 1} & \text{Column 2} & \text{Column 3} & \text{Column 4} \\ \hline \text{Row 1} & & & (1,1), (2,1) & (1,2), (1,3), (1,4), (2,2), (2,3), (2,4) \\ \hline \text{Row 2} & & & (3,1) & (3,2), (3,3), (3,4) \\ \hline \text{Row 3} & & & & \\ \hline \end{array}$$

After the command S, they move southward again.

$$\begin{array}{|c|c|c|c|c|} \hline & \text{Column 1} & \text{Column 2} & \text{Column 3} & \text{Column 4} \\ \hline \text{Row 1} & & & & \\ \hline \text{Row 2} & & & (1,1), (2,1) & (1,2), (1,3), (1,4), (2,2), (2,3), (2,4) \\ \hline \text{Row 3} & & & (3,1) & (3,2), (3,3), (3,4) \\ \hline \end{array}$$

After the command W, they move westward again.

$$\begin{array}{|c|c|c|c|c|} \hline & \text{Column 1} & \text{Column 2} & \text{Column 3} & \text{Column 4} \\ \hline \text{Row 1} & & & & \\ \hline \text{Row 2} & & (1,1), (2,1) & (1,2), (1,3), (1,4), (2,2), (2,3), (2,4) & \\ \hline \text{Row 3} & & (3,1) & (3,2), (3,3), (3,4) & \\ \hline \end{array}$$

The final position of AA gun which originally placed at coordinate $(1,1)$ is at cell $(2,2)$, which is $1 \times 4 + 1=5$.

Scoring

Subtask 1 (10 points): $nmT \leq 10^6$

Subtask 2 (22 points): $n=1$

Subtask 3 (23 points): $S$ only consists of the characters $\tt{N}$ and $\tt{E}$.

Subtask 4 (45 points): No additional constraints.