URI Online Judge | 1121

Sticker Collector Robot

Maratona de Programação da SBC Brazil

Timelimit: 1

One of the favorite sports in RoboLand is the Robots Rally. This rally is practiced in a giant rectangular arena of square cells with dimensions N rows by M columns. Some cells are empty, some contain a sticker for the World Footbal Cup Album (much appreciated by artificial intelligences in RoboLand) and some are occupied by pillars which support the roof of the arena. During the rally the robots can occupy any cell in the arena, except those containing pillars, since they block the robot movement. The path of the robot in the arena during the rally is determined by a sequence of instructions. Each instruction is represented by one of the following characters: 'D', 'E' and 'F', meaning, respectively, "turn 90 degrees to the right", "turn 90 degrees to the left" and "move forward one cell". Robots start the rally in some initial position in the arena and follow closely the sequence of instructions given (after all, they are robots!). Whenever a robot occupies a cell that contains a Cup sticker he collects it. Stickers are not replaced, that is, each scticker can be collected only once. When a robot tries to move into a cell which contains a pillar he stalls, remaining in the cell where he was, with the same orientation. The same happens when a robot tries to leave the arena.

Given the map of the arena, describing the position of pillars and sctickers, and the sequence of instructions of a robot, you must write a program to determine the number of stickers collected by the robot.

Input

The input contains several test cases. The first line of a test case contains three integers N, M and S (1 ≤ N, M ≤ 100, 1 ≤ S ≤ 5 × 104 ), separated by white spaces, indicating respectively the number of rows, the number of columns of the arena and the number of instructions to the robot. Each of the following N lines describes a cell line of the arena and contains a string with M characters. The first line to appear in the description of the arena is the one more to the North, the first column to appear in description of a cell line of the arena is the one more to the West.

Each cell in the arena is described by one of the following characters:


The last line in the input contains a sequence of S characters among `D', `E' and `F', representing the instructions to the robot.

The last test case is followed by a line which contains only three numbers zero separated by a blank space.

Output

For each rally described in the input your program must print a single line containing a single integer indicating the number of stickers that the robot collected during the rally.

Input Sample Output Sample

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

0
1
3