说明

巨龙 Evirir 再次围攻 MCO 大陆。为了抵御 Evirir 的进攻，MCO 大陆的居民们准备了配备破龙鳞弹药的防空炮。

MCO 大陆可以建模为一个 $n$ 行 $m$ 列的网格，行从上到下编号为 $1$ 到 $n$，列从左到右编号为 $1$ 到 $m$。位于第 $i$ 行、第 $j$ 列的单元格记作 $(i,j)$。每个单元格中都有一门防空炮。为了更好地击落巨龙 Evirir，火炮将跟随 Evirir 在 MCO 大陆上空的飞行轨迹进行移动。

MCO 大陆的前任总统 Duckmoon 将向居民们下达一系列共 $T$ 条指令，指示火炮移动。这些指令由一个长度为 $T$ 的字符串 $S$ 给出，该字符串由字符 $\tt{N}$、$\tt{S}$、$\tt{E}$ 和 $\tt{W}$ 组成。在第 $i$ 条指令（由 $S_i$ 表示）中，MCO 大陆上的所有火炮将按如下方式移动：

• 若 $S_i = \tt{N}$，火炮向北移动。位于 $(i,j)$ 的火炮，若 $i > 1$ 则移动到 $(i-1,j)$；否则保持不动。
• 若 $S_i = \tt{S}$，火炮向南移动。位于 $(i,j)$ 的火炮，若 $i < n$ 则移动到 $(i+1,j)$；否则保持不动。
• 若 $S_i = \tt{E}$，火炮向东移动。位于 $(i,j)$ 的火炮，若 $j < m$ 则移动到 $(i,j+1)$；否则保持不动。
• 若 $S_i = \tt{W}$，火炮向西移动。位于 $(i,j)$ 的火炮，若 $j > 1$ 则移动到 $(i,j-1)$；否则保持不动。

注意，一个单元格内可以同时有多门火炮。

在巨龙 Evirir 被击落后，MCO 大陆的居民需要将防空炮收好。对于每一对 $(i,j)$（$1 \leq i \leq n$，$1 \leq j \leq m$），MCO 大陆的居民想知道原本位于 $(i,j)$ 的火炮在执行完所有 $T$ 条指令后最终会移动到哪个单元格。

每个火炮的最终位置用一个整数来描述。若一门火炮最终位于单元格 $(x, y)$，则其最终位置表示为整数 $(x - 1) \times m + (y - 1)$。

输入格式

第一行包含三个以空格分隔的整数 $n, m$ 和 $T$，分别表示网格的行数、列数以及 Duckmoon 下达的指令数量。保证 $1 \leq n, m, T \leq 10^6$ 且 $nm \leq 10^6$。

第二行包含一个长度为 $T$ 的字符串 $S$，由字符 $\tt{N}$、$\tt{S}$、$\tt{E}$ 和 $\tt{W}$ 组成。

输出格式

令 $(x_{i,j},y_{i,j})$ 为原本位于单元格 $(i,j)$ 的火炮最终所在的单元格。

输出 $n$ 行。对于第 $i$ 行，输出 $m$ 个以空格分隔的整数 $q_{i,1},q_{i,2},...,q_{i,m}$，其中 $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

提示

注释

以下是示例 1 的可视化过程，展示了原始防空炮的坐标以及它们根据指令移动的方式。

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

执行指令 N 后，火炮向北移动。

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

执行指令 E 后，火炮向东移动。

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

再次执行指令 E 后，火炮继续向东移动。

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

执行指令 S 后，火炮向南移动。

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

执行指令 W 后，火炮向西移动。

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

最初位于坐标 $(1,1)$ 的防空炮最终位于单元格 $(2,2)$，其对应的整数值为 $1 \times 4 + 1 = 5$。

计分

子任务 1 （$10$ 分）： $nmT \leq 10^6$

子任务 2 （$22$ 分）： $n=1$

子任务 3 （$23$ 分）： $S$ 仅由字符 $\tt{N}$ 和 $\tt{E}$ 组成

子任务 4 （$45$ 分）： 无额外限制

翻译由 DeepSeek 完成