龙 Evirir 再次对 MCO 国发动了攻击。为了抵御 Evirir 的进攻，MCO 国的居民准备了配备穿透龙鳞弹药的防空炮。

MCO 国可以被建模为一个 $n \times m$ 的网格，行从上到下编号为 $1$ 到 $n$，列从左到右编号为 $1$ 到 $m$。第 $i$ 行第 $j$ 列的格子记为 $(i, j)$。每个格子中都有一门防空炮。为了更好地击落 Evirir，这些防空炮会随着它在 MCO 国上空飞行而移动。

MCO 国前总统 Duckmoon 会向居民发布 $T$ 条指令，指示他们移动防空炮。这些指令由一个长度为 $T$ 的字符串 $S$ 表示，其中只包含字符 N、S、E 和 W。在第 $i$ 条指令（即 $S_i$）执行时，所有防空炮按如下方式移动：

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

注意，一个格子中可以同时存在多门防空炮。

当 Evirir 被击落后，MCO 国居民需要收回所有防空炮。对于每一对 $(i, j)$（$1 \le i \le n$，$1 \le j \le m$），居民想知道最初位于 $(i, j)$ 的防空炮在执行完全部 $T$ 条指令后最终会停留在哪个格子。

每门防空炮的最终位置用一个整数表示。若某门防空炮最终位于 $(x, y)$，则其对应的整数为 $(x - 1) \times m + (y - 1)$。

输入格式

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

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

输出格式

设 $(x_{i,j}, y_{i,j})$ 表示最初位于 $(i, j)$ 的防空炮最终到达的格子。

输出 $n$ 行。第 $i$ 行输出 $m$ 个以空格分隔的整数 $q_{i,1}, q_{i,2}, \dots, q_{i,m}$，其中：

$q_{i,j} = (x_{i,j} - 1) \times m + (y_{i,j} - 1)$。

子任务

• 子任务 1（10 分）：$nmT \le 10^6$
• 子任务 2（22 分）：$n = 1$
• 子任务 3（23 分）：$S$ 仅包含字符 N 和 E
• 子任务 4（45 分）：无额外限制

样例数据

输入

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 的示意图，展示了最初每门防空炮的位置以及它们根据指令移动的过程。

初始状态：

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

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

再次执行指令 E 后，再次向东移动。

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

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

最终，原本位于 $(1,1)$ 的防空炮停在 $(2,2)$，对应的整数为 $1 \times 4 + 1 = 5$。