[요약 중] 요약] K개의 N행 M열 격자가 주어진다. 1번째 상태에서, K개의 박테리아의 위치와 보고 있는 방향이 주어진다.
박테리아가 각 상태마다 아래 방법으로 움직일 때 K개의 박테리아가 전부 (X, Y)에 도달할 때의 상태 번호를 구하여라.

1. 박테리아는 자신이 위치한 격자에 쓰여진 수 X를 본다.
2. 박테리아가 시계 방향으로 X*90도 회전한다.
3. 박테리아가 보고 있는 방향이 격자 밖이면 180도 회전한다.
4. 박테리아가 보고 있는 방향으로 한 칸 움직인다.

Each bacterium begins its adventure in a certain cell, facing one of the four neighbouring cells, and carries out the following actions every second:

1. Reads the number X dedicated to that bacterium in the current cell.
2. Turns 90 degrees clockwise, X times.
3. If it is facing a cell outside the board, it turns 180 degrees.
4. Finally, it moves to the cell that it is facing.

Since Luka only has two hours of chemistry class today, help him determine how long the game will last, in seconds.

입력

• The first line of input contains the positive integers N (3 ≤ N ≤ 50), M (3 ≤ M ≤ 50), and K (1 ≤ K ≤ 5).
• The second line of input contains the positive integers X and Y, the row and column where Luka has placed the trap. The remainder of the input consists of bacteria descriptions, for each bacterium i from 1 to K:
  • - two positive integers Xi , Yi - the row and column of the starting cell of bacterium i, and the character Ci representing the starting direction that the bacterium is facing (U - up, R - right, D - down, L - left).
  • - N by M matrix of digits between 0 and 9, inclusive; the digit in row x and column y represents the number in cell (x, y) dedicated to bacterium i.

출력

입출력 예

input

3 3 1
2 2
1 1 R
010
000
000

output

3

input

3 4 2
2 2
3 4 R
2327
6009
2112
3 2 R
1310
2101
1301

output

8

input

4 4 3
4 3
1 1 U
1001
0240
3322
2327
1 3 L
9521
2390
3020
2421
2 2 D
3397
2013
1102
7302

output

296

입력 예 1 설명

• 0초 : 로봇이 (1, 1)에 있다.
• 1초 : 로봇이 (1, 2)로 움직인다.
• 2초 : 로봇이 (2, 2)로 움직인다.
• 3초 : 로봇 충전이 완료되었다.

출처:coci/2012-2013/contest6
요약:functionx