Problem D
Buggy Rover

Mars rover being tested near the Paranal Observatory.
CC BY-SA 4.0 by ESO/G.
Hudepohl on Wikimedia Commons

Today marks the launch of their brand-new Hornet rover. The rover is set to explore the planet using a simple algorithm. Internally, the rover maintains a direction ordering, a permutation of the directions north, east, south, and west. When the rover makes a move, it goes through its direction ordering, chooses the first direction that does not move it off the face of the planet or onto an impassable rock, and makes one step in that direction.

Between two consecutive moves, the rover may be hit by a cosmic ray, replacing its direction ordering with a different one. ICPC scientists have a log of the rover’s moves, but it is difficult to determine by hand if and when the rover’s direction ordering changed. Given the moves that the rover has made, what is the smallest number of times that it could have been hit by cosmic rays?

Input

The first line of input contains two integers $r$ and $c$, where $r$ ($1 \leq r \leq 200$) is the number of rows on the planet, and $c$ ($1 \leq c \leq 200$) is the number of columns. The rows run north to south, while the columns run west to east.

The next $r$ lines each contain $c$ characters, representing the layout of the planet. Each character is either ‘#’, a rocky space; ‘.’, a flat space; or ‘S’, a flat space that marks the starting position of the rover. There is exactly one ‘S’ in the grid.

The following line contains a string $s$, where each character of $s$ is ‘N’, ‘E’, ‘S’, or ‘W’, representing the sequence of the moves performed by the rover. The string $s$ contains between $1$ and $10\, 000$ characters, inclusive. All of the moves lead to flat spaces.

Output

Output the minimum number of times the rover’s direction ordering could have changed to be consistent with the moves it made.

5 3
#..
...
...
...
.S.
NNEN

1

3 5
.###.
....#
.S...
NEESNS

0

3 3
...
...
S#.
NEESNNWWSENESS

4