Problem Background

After breakfast, the little ones went to the playground for basic training, and William took the opportunity to occupy the kitchen. He put on an apron over his military uniform, tied a triangular scarf on his head, and placed a large number of ingredients bought early in the morning from the market on the table. Then, William baked a large number of cream cakes.

William placed the cream cakes on the table. Chtholly smelled the aroma of the cakes and couldn't wait to rush to the table to enjoy this feast. However, the cake-making process seemed to be missing that final step...

"Wait a moment, I haven't added the cream yet," William said, picking up the piping bag.

But Chtholly, who was already starving, couldn't wait for all the cream to be added. While William was busy squeezing white cream onto each cake, Chtholly had already secretly picked up a piece of cake...

Problem Description

The cakes on the table can be considered as an infinite Cartesian coordinate system, with each cake located at an integer coordinate point.

Each minute, William adds several layers of cream to each cake according to the following rules: If a cake has not been eaten by Chtholly for the $i$-th consecutive time, then $i$ layers of cream are added to the cake.

After William finishes squeezing cream on all the cakes, Chtholly picks up a cake and eats one layer of cream from it. Specifically, if Chtholly eats a layer of cream from a cake, William immediately adds another layer of cream to that cake, which does not count towards the consecutive times it has not been eaten (i.e., the next $i$ remains as $1$).

With so many cakes, Chtholly doesn't know where to start, so she decides to sample them in a moving pattern. There are a total of $m$ minutes, and Chtholly's cake-eating sequence can be expressed as a string of length $m$. The $t$-th character can be N, S, W, E, indicating that Chtholly will eat the cake above, below, to the left, or to the right of the cake she ate in the $t$-th minute in the $(t+1)$-th minute.

Chtholly picks up the cake at point $(x,y)$ in the first minute, as the cake currently has no cream on it, so Chtholly does not sample it, and William does not immediately add cream to it.

Chtholly wants to know how many layers of cream are left on each cake after $m$ minutes.

In this problem, up and right refer to the positive directions of the $y$ and $x$ axes, respectively.

Brief Problem Statement:

There is an $n \times n$ grid where a ground that has not been walked on for $i$ consecutive minutes accumulates $i$ units of dust in the $i$-th minute. Walking on it does not accumulate dust, but the dust does not reset either; it starts accumulating dust again one unit per minute after the first minute of not being walked on. Someone moves within this $n \times n$ range, and their movement path can be described by a string of N, S, W, E, each representing up, down, left, and right. This person starts at point $(x,y)$ and moves one step per minute.

Determine the amount of dust accumulated on each position after the final move.

The person does not move out of the grid.

Input Format

The first line contains four positive integers $n, m, x, y$, where $x, y$ represent the coordinates, not array indices.
The second line contains a string of length $m$, representing Chtholly's movement sequence.

Output Format

Output consists of $n$ lines, each containing $n$ numbers. The $j$-th number on the $i$-th line represents the amount of dust at coordinate $(j, n-i+1)$.

Sample Input and Output

Sample Input #1

5 4 1 1
NENW

Sample Output #1

10 10 10 10 10 
10 10 10 10 10 
10 6 10 10 10 
4 4 10 10 10 
6 10 10 10 10 

Sample Input #2

7 14 1 1
NENENENENESSSS

Sample Output #2

105 105 105 105 105 105 105 
105 105 105 105 55 61 105 
105 105 105 49 51 69 105 
105 105 51 49 105 79 105 
105 61 55 105 105 91 105 
79 69 105 105 105 105 105 
91 105 105 105 105 105 105 

Sample Input #3

10 70 2 2
NWSNSNNNSNNSSNNSENNNNEESNWSESESSWENNSEWESWWWESEEESENNSENWNESNWSNNNEESS

Sample Output #3

2485 2485 2485 2485 2485 2485 2485 2485 2485 2485 
2485 1407 1205 1267 2485 2485 2485 2485 2485 2485 
2485 1435 1281 1167 2485 2485 2485 2217 2281 2347 
2485 1465 2485 1255 1041 2485 2485 2155 2485 2415 
1557 1497 2485 2485 969 1177 2485 1733 1807 2485 
1471 1531 1315 907 935 1267 2485 1473 1647 2485 
1631 2485 2485 1357 1381 1407 1435 1499 1645 2485 
2021 2347 2485 2485 2485 2485 1465 1497 2485 2485 
2087 2415 2485 2485 2485 2485 2485 2485 2485 2485 
2485 2485 2485 2485 2485 2485 2485 2485 2485 2485 

Sample Input #4

5 4 2 1
NENW

Sample Output #4

10 10 10 10 10 
10 10 10 10 10 
10 10 6 10 10 
10 4 4 10 10 
10 6 10 10 10 

Notes

The y-axis points up, the x-axis points right, and the bottom left corner of the sample output represents $(1,1)$. Chtholly is at the initial point in the first minute, moves to the corresponding position in the second minute, and moves to the last point in the $(m+1)$-th minute, but there are only $m$ minutes in total, so the last point is not affected by the movement.

Sample 1 Explanation:

Chtholly's movement path is $(1,1) \rightarrow (1,2) \rightarrow (2,2) \rightarrow (2,3) \rightarrow (1,3)$, totaling $4$ minutes.

For the $1$-st minute, $(1,1)$ cream layers remain unchanged, and other points get $1$ layer of cream.

For the $2$-nd minute, $(1,2)$ cream layers remain unchanged, $(1,1)$ gets $1$ layer of cream, and other points get $2$ layers of cream.

For the $3$-rd minute, $(2,2)$ cream layers remain unchanged, $(1,1)$ gets $2$ layers of cream, $(1,2)$ gets $1$ layer of cream, and other points get $3$ layers of cream.

For the $4$-th minute, $(2,3)$ cream layers remain unchanged, $(1,1)$ gets $3$ layers of cream, $(1,2)$ gets $2$ layers of cream, $(2,2)$ gets $1$ layer of cream, and other points get $4$ layers of cream.

Note that Chtholly finally moves to $(1,3)$, but there are only $4$ minutes, so $(1,3)$ is not actually affected. The initial point is not necessarily at $(1,1)$.

$1 \leq n \leq 50, 1 \leq m \leq 1000$.

见题面 Input 部分

见题面 Output 部分