#215425. [MCO 2024] Dragon Attack

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 by grid with the rows labeled to from top to bottom and columns labeled to from left to right. The cell in the row, and the column is denoted by . 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 commands to the inhabitants, directing them to move guns. These directions are specified in a string of length , which is composed of the characters , , , and . At the command, represented by , all the guns in MCO land will move in the following manner:

• If , guns are directed northward. A gun at position moves to if ; otherwise, it remains stationary.
• If , guns are directed southward. A gun at position moves to if ; otherwise, it remains stationary.
• If , guns are directed eastward. A gun at position moves to if ; otherwise, it remains stationary.
• If , guns are directed westward. A gun at position moves to if ; 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 with , , the inhabitants of MCO land want to know which cell the gun originally in will end up in after all commands.

An integer is used to describe the final position of each gun. If a gun ends up in cell , its final position is represented by the integer .

The first line consists of three space-separated integers and denoting the number of rows, number of columns, and number of commands given by Duckmoon respectively. It is guaranteed that and .

The second line contains a string of length consisting of the characters .

Let be the cell the gun originally in cell ends up in.

Output lines. For the line, output space-separated integers where .

样例输入 1

3 4 5
NEESW

样例输出 1

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

样例输入 2

7 5 20
WSSWNSENSNWENESSNSEW

样例输出 2

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

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.

After the command N, they move northward.

After the command E, they move eastward.

After the command E, they move eastward again.

After the command S, they move southward again.

After the command W, they move westward again.

The final position of AA gun which originally placed at coordinate is at cell , which is .

Scoring

Subtask 1 (10 points):

Subtask 2 (22 points):

Subtask 3 (23 points): only consists of the characters and .

Subtask 4 (45 points): No additional constraints.