Collector Robot

Time limit2sMemory limit512 MB

Summary

Simulate a robot moving on a grid with pillars, turning and stepping according to a given instruction string, and count the distinct stickers it visits.

Level: Easy3 of 10
Topics: Simulation, Implementation
Solved: No attempts yet

Problem

Robot Rally is one of the popular sports in Robotland. The rally runs in a giant rectangular arena of $N$ rows by $M$ columns of square cells. Some cells are empty, some hold a World Cup sticker (much liked by the artificial intelligences of Robotland), and some are taken by pillars that hold up the arena roof. A robot may enter any cell of the arena except a cell with a pillar, and a pillar blocks its movement.

The route a robot takes during the rally is set by a sequence of instructions. Each instruction is one of the characters D, E, and F, meaning turn 90 degrees right, turn 90 degrees left, and move forward one cell.

The robot starts from a given position in the arena and carries out the given instructions in order, exactly as written. Whenever the robot occupies a cell that holds a sticker, it collects that sticker. Stickers are never replaced, so each sticker is collected only once. When a robot tries to move into a cell with a pillar it skids, staying in the cell it was in with the same orientation. The same happens when a robot tries to leave the arena.

Given the arena map with the positions of the pillars and the stickers, and the instruction sequence of one robot, write a program that computes the number of stickers the robot collects.

Input

The input holds several test cases. The first line of a test case holds three integers $N$ , $M$ , and $S$ ( $1 \le N, M \le 100$ , $1 \le S \le 5 \times 10^4$ ) separated by blanks: the number of rows of the arena, the number of columns of the arena, and the number of instructions given to the robot.

Each of the next $N$ lines describes one row of arena cells and holds a string of $M$ characters. The first row in the description is the northernmost one, and the first column of a row is the westernmost one.

Each arena cell holds one of the following characters.

. a normal cell
* a cell that holds a World Cup sticker
# a cell that holds a pillar
N, S, L, O the cell where the robot starts, unique in the arena. The letter gives the initial orientation of the robot: N is north, S is south, L is east, and O is west.

The last line of a test case holds a sequence of $S$ characters drawn from D, E, and F, the instructions for the robot.

The last test case is followed by a line that holds only three zeros separated by a single blank.

Output

For each rally described in the input, print one line with one integer, the number of stickers the robot collected during that rally.

Examples2

Example 1

Input

3 3 2
***
*N*
***
DE
4 4 5
...#
*#O.
*.*.
*.#.
FFEFF
10 10 20
....*.....
.......*..
.....*....
..*.#.....
...#N.*..*
...*......
..........
..........
..........
..........
FDFFFFFFEEFFFFFFEFDF
0 0 0

Expected output

0
1
3

Example 2

Input

2 1 1
*
N
F
2 1 1
S
*
F
1 2 1
L*
F
1 2 1
*O
F
0 0 0

Expected output