P15280 [MCO 2024] Dragon Attack

巨龙 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)$。

#### 注释 以下是示例 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 完成