문제
N행 M열의 격자에 K개의 로봇이 있다. 각 로봇은 내장된 정보에 따라(각 로봇마다 다르다) 다음과 같은 방식으로 움직인다.
1) 로봇은 자신이 위치한 격자의 X값을 읽어 들인다. 2) 시계방향으로 90도 회전하는 것을 X번 한다. 3) 만약 로봇이 격자 밖을 바라보고 있다면 180도 회전한다. 4) 자신이 바라보는 방향으로 한 칸 움직인다.
로봇은 회전을 엄청 빨리 할 수 있기 때문에 로봇이 회전하는 시간은 무시할 수 있다.
한편 로봇이 한 칸 움직이는 데 걸리는 시간은 1초이다.
로봇의 주인인 제노는 K개의 로봇들의 배터리 잔량이 부족한 것을 깨달았다!
하지만 로봇이 작동 중일 때에는 로봇을 조종할 수 없게 설계되었기 때문에 로봇들이 알아서 충전기로 와야 한다.
그러나 충전기는 K개의 로봇이 모두 올 때만 작동한다.
제노는 충전기도 비싼 돈으로 사들인 만큼 성능이 엄청나기 때문에, 충전을 시작하면 정확히 1초 만에 로봇이 충전이 된다.
이 때, 제노의 로봇이 모두 충전될 때까지 걸리는 시간을 구하는 프로그램을 작성하여라.
입력
첫 번째 줄에는 N, M, K가 주어진다. (3 ≤ N, M ≤ 50, 1 ≤ K ≤ 5)
두 번째 줄에는 충전기의 행 번호와 열 번호가 주어진다.
세 번째 줄부터는 K개의 로봇에 대한 정보가 주어진다.
각 로봇에 대하여, 첫 번째 줄에는 처음 위치(행 번호와 열 번호)와 로봇의 방향(U - 위, R - 오른쪽, D - 아래, L - 왼쪽)이 주어진다.
두 번째 줄부터 N개의 줄에는 각 격자의 X값이 공백 없이 주어진다. X값은 0~9 사이의 정수이다.
출력
예제1
331
22
11R
010
000
000
3
예제2
342
22
34
2327
6009
2112
32
1310
2101
1301
8