URI Online Judge | 2156

The Adventures of Pak-man

By Ricardo Martins, IFSULDEMINAS BR Brazil

Timelimit: 1

Once a new game needed to be developed. Here, the players would control Pak-man, in order to eat all the pads that are scattered in a maze while avoiding four ghosts escaping from a prison. In each corner of the playing area are larger inserts that allow Pak-man hunting ghosts, instead of being hunted for a short period of time. In a first stage of the game, without the ghosts and no larger tablets, you were assigned to develop a program that, given a certain scenario, and a series of movements, tell how many tablets have been eaten.

Write a program that, given a scenario and instructions movements, tell how many tablets were eaten in the game.

Input

There will be several test cases. Each test case begins with three integer values, L (3 ≤ L ≤ 100), C (3 ≤ C ≤ 100) and I (3 ≤ I ≤ 10000), indicating the number of rows and columns of the setting and the amount of instructions. Then have L lines and C columns, informing the scenario, which will only # where is the wall, where * is a tablet, <where is the Pak-man and space, places the Pak-man can move. The next line is I characters, with the Pak-man move instructions, which L, R, U and D indicates the direction which the Pak-man is directed (L-Left, R-Right, U-Up, D-Down) and W means that the Pak-man will move toward a position in which it stands. If he is walking and the desired location for a wall, it goes nowhere. If a tablet, he eats the tablet and where it was gum becomes a free space and it is the place of the tablet. If a space he goes to the desired location. The final entry is three zeros. Detail: Pak-man will always get a new scenario facing right.

Output

For each test case, print an integer value with the amount of tablets.

##########

#<*******#

##########

UWWRWW

In this example, the Pak-man turns up , tries to walk two places, but as there is wall, is in the same place. Then turn right and walk two places, eating, with this two tablets.

Input Sample Output Sample

7 7 15

#######

#<#* *#

#*# # #

# #*#*#

#*# # #

# * #*#

#######

DWWWWRWWUWWWWRW

3 10 10

##########

#<*******#

##########

WLRUDRWWWW

0 0 0

5

5