K. Larila
time limit per test
2 с
memory limit per test
256 megabytes
input
standard input
output
standard output

Chief Scientist Randward Lirili want to explore a $$$N \times N$$$ grid on Larila using rovers.

Due to the high cost, each rover is programmable, but only with a sequence of $$$M$$$ instructions moving the rover North (N), East (E), South (S), or West (W). The rover repeats this sequence of instructions infinitely.

Some of the tiles on the grid are too precarious for the rover to travel through, if the rover needs to execute an instruction that will cause the rover to travel onto one of these tiles, the rover will skip this instruction and go to the next one. Moving outside of the grid is also considered precarious.

The rover is said to have returned to base if the rover reaches one of the ships that have landed in this grid. When the rover reaches the ship, it stops.

Given a sequence of instructions, determine whether a rover will return to base for every starting tile on the grid. If a rover starts on a tile that is precarious, it crashes and burns and automatically fails to return to base.

Input

The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \le N, M \le 500$$$).

Each of the next $$$N$$$ lines contains a string of $$$N$$$ characters describing a row of the grid, from north to south. Each character is one of . (safe), # (precarious), or S (ship).

The last line contains a string of $$$M$$$ characters describing the move sequence. Each character is one of N (north), S (south), E (east), or W (west).

Output

Print $$$N$$$ lines, each containing $$$N$$$ characters. The character at row $$$i$$$, column $$$j$$$ should be 1 if a rover starting at that cell returns to base, and 0 otherwise.

Example
Input
3 4
S..
#.#
...
NNWW
Output
111
010
010
Note
  • $$$(1,1)$$$ is a ship — returned to base immediately.
  • $$$(1,2)$$$ and $$$(1,3)$$$: already on row 1, so N moves do nothing. Then W moves slide them toward $$$(1,1)$$$, the sink.
  • $$$(2,1)$$$ and $$$(2,3)$$$ are precarious — output 0.
  • $$$(2,2)$$$: N goes to $$$(1,2)$$$, then N does nothing (already row 1), then WW slides to $$$(1,1)$$$. Escapes.
  • $$$(3,1)$$$: N would go to $$$(2,1)$$$, which is precarious. So N does nothing, N does nothing, W does nothing (already column 1), W does nothing. After one cycle it is still at $$$(3,1)$$$. Stuck forever — output 0.
  • $$$(3,2)$$$: NN goes to $$$(1,2)$$$, WW slides to $$$(1,1)$$$. Escapes.
  • $$$(3,3)$$$: N would go to $$$(2,3)$$$ — precarious, blocked. Stays at $$$(3,3)$$$. Repeats forever — output 0.