Dust Accumulation on a Grid

We are given an (n \times n) grid and a process of dust accumulation. Initially, all cells have no dust. In each minute, every cell that is not visited by a person gains dust. The amount of dust deposited on a cell depends on how long it has been since a person last visited that cell. In particular, if a cell has not been visited for (i) consecutive minutes, then in the (i)th minute it gains (i) units of dust. When a cell is visited by the person in a minute, no dust is deposited in that minute and the cell’s "waiting time" counter is reset to (0) (so that in the subsequent minutes, if it is not visited, dust accumulation resumes starting from (1) unit in the first minute, (2) units in the next, and so on).

The person starts at position ((x,y)) in minute 1. Then, for a total of (m) minutes, the person moves within the grid. The movement is given by a string of length (m-1) consisting of the characters N, S, W, E – which indicate a move one step to the north (increasing (y)), south (decreasing (y)), west (decreasing (x)), and east (increasing (x)) respectively. It is guaranteed that the person never leaves the grid.

For every cell the dust is accumulated only during the minutes when it was not visited. That is, if a cell is not visited consecutively for (L) minutes, then the total dust deposited on that cell during that interval is given by (\sum_{i=1}^{L} i = \frac{L(L+1)}{2}). If a cell is visited at minute (t), then the dust deposition for that minute is skipped and the waiting counter is reset. Your task is to compute, after (m) minutes, the total amount of dust deposited on every cell of the grid.

Note: The grid’s coordinates are defined in a standard Cartesian manner: the positive (x) direction is to the right and the positive (y) direction is upward. The output should display the grid row by row starting from the top (i.e. (y=n)) to the bottom (i.e. (y=1)), and within each row, from left ((x=1)) to right ((x=n)).

inputFormat

The input consists of the following:

• The first line contains two integers (n) and (m) ((1 \leq n \leq 1000,\ 1 \leq m \leq 10^5)), representing the size of the grid and the total number of minutes.
• The second line contains two integers (x) and (y) ((1 \leq x, y \leq n)), the starting coordinates of the person.
• The third line contains a string of length (m-1) composed of the characters N,S,W,E, representing the moves made by the person from minute 2 to minute (m). It is guaranteed that the person never moves outside the grid.

outputFormat

Output (n) lines, each containing (n) integers. The (j)th number on the (i)th line (when counting lines from top to bottom) represents the total dust accumulated on the cell at coordinates ((j, n-i+1)).

sample

3 3
2 2
NE

6 2 3
6 3 6
6 6 6