Background

After breakfast, the little ones all went to the playground for basic training, and William took the chance to occupy the kitchen.
He wore an apron over his uniform, tied a triangular headscarf on his head, and laid out a large amount of ingredients he had bought from the market early in the morning on the table.
Then, William baked a large number of cream cakes.

William placed the cream cakes on the table. When Chtholly smelled the fragrance of the cakes, she could not wait and pounced on the dining table to enjoy this feast. However, the cake-making seemed to be missing the very last step...
“Wait a moment, I haven’t piped the cream on yet.” William said as he picked up the piping bag.

But how could the hungry Chtholly wait for all the cream to be piped?
While William was still busy piping white cream onto each cake one by one, Chtholly had already secretly picked up a cake...

Problem Description

The cakes on the table can be seen as an infinite Cartesian coordinate plane, and each cake is located at an integer lattice point on the plane.

Every minute, William will spread several layers of cream on every cake, with the following rule: if a cake has not been eaten by Chtholly for the consecutive $i$-th time, then $i$ layers of cream will be piped onto that cake.

Each time after William finishes piping cream on all cakes, Chtholly will pick up one cake and eat one layer of cream from that cake. In particular, if Chtholly eats one layer of cream from a cake, William will immediately kindly add one layer back onto that cake, and this does not count into the number of consecutive times it has not been eaten (that is, the next $i$ is still $1$).

Because there are too many cakes, Chtholly really does not know where to start, so she decides to taste them by moving.
There are $m$ minutes in total. Chtholly’s cake-eating sequence can be represented by a string of length $m$. The $t$-th character may be N, S, W, E, indicating that in minute $t+1$, Chtholly will eat the cake that is above, below, left, or right of the cake eaten in minute $t$.
In minute $1$, Chtholly will pick up the cake at point $(x,y)$. Since the cake currently has no cream piped on it, Chtholly will not taste it, and William will not immediately add cream to it either.

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 direction of the $y$-axis and the positive direction of the $x$-axis, respectively.

Simplified statement:

There is an $n \times n$ area. If a cell has not been passed through for consecutive $i$ minutes, then in the $i$-th minute, $i$ units of dust will fall onto it. When someone passes through, no dust falls, but the dust is not cleared. In the first minute after the person leaves, 1 unit of dust will fall again, and so on. A person moves within this $n \times n$ range; the movement path can be described by a string consisting of $\text{N,S,W,E}$, where each letter means up, down, left, right. This person starts at point $(x,y)$ and moves one step per minute.

Find the amount of dust that falls on each position in the end.

It is guaranteed that this person never moves outside the range.

Input Format

The first line contains four positive integers $n,m,x,y$, with meanings as described above, where $x,y$ are the horizontal and vertical coordinates, not array indices.
The second line contains a string of length $m$, representing Chtholly’s movement sequence.

Output Format

Output $n$ lines, each with $n$ numbers. The $j$-th number in the $i$-th line indicates the amount of dust at coordinate $(j,n-i+1)$.

5 4 1 1
NENW

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 

7 14 1 1
NENENENENESSSS

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 

10 70 2 2
NWSNSNNNSNNSSNNSENNNNEESNWSESESSWENNSEWESWWWESEEESENNSENWNESNWSNNNEESS

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 

5 4 2 1
NENW

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 

Hint

In this problem, the $y$-axis points upward and the $x$-axis points to the right. In the sample output, the bottom-left corner represents $(1,1)$. In minute 1, Chtholly is at the starting point; in minute 2, she moves to the corresponding position; in minute $m+1$, she moves to the final point, but there are only $m$ minutes in total, so the final point is not affected by the movement.

Explanation for Sample 1:

Chtholly’s movement path is $(1,1)\rightarrow(1,2)\rightarrow(2,2)\rightarrow(2,3)\rightarrow(1,3)$, for a total of $4$ minutes.

For minute $1$, the cream layers at $(1,1)$ do not change, and all other points are piped with $1$ layer of cream.

For minute $2$, the cream layers at $(1,2)$ do not change, $(1,1)$ is piped with $1$ layer of cream, and all other points are piped with $2$ layers of cream.

For minute $3$, the cream layers at $(2,2)$ do not change, $(1,1)$ is piped with $2$ layers of cream, $(1,2)$ is piped with $1$ layer of cream, and all other points are piped with $3$ layers of cream.

For minute $4$, the cream layers at $(2,3)$ do not change, $(1,1)$ is piped with $3$ layers of cream, $(1,2)$ is piped with $2$ layers of cream, $(2,2)$ is piped with $1$ layer of cream, and all other points are piped with $4$ layers of cream.

Note that finally Chtholly moved to $(1,3)$, but the time is only $4$ minutes, so it will not actually affect $(1,3)$. The starting point is not necessarily at $(1,1)$.

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

Translated by ChatGPT 5