박테리아

$N$행 $M$열로 나뉜 실험판이 있다. 가장 위쪽 행이 $1$번, 가장 아래쪽 행이 $N$번이고, 가장 왼쪽 열이 $1$번, 가장 오른쪽 열이 $M$번이다.

이 실험판 위에 지능이 있는 박테리아 $K$마리를 올려놓는다. 각 박테리아는 지정된 칸에서 시작하며, 위·아래·왼쪽·오른쪽 중 한 방향을 바라보고 있다. 박테리아는 매 초마다 아래 동작을 순서대로 한 번씩 수행한다.

1. 현재 있는 칸에 적힌 숫자 $X$를 읽는다. 이 숫자는 박테리아마다 다르며, 각 박테리아는 자신에게 해당하는 숫자를 읽는다.
2. 시계 방향으로 $90^\circ$씩 $X$번 회전한다.
3. 바라보는 방향의 칸이 실험판 밖이면, $180^\circ$ 회전한다.
4. 바라보는 칸으로 한 칸 이동한다.

실험판의 어떤 한 칸에는 덫이 설치되어 있다. 박테리아를 처음 올려놓은 상태를 $1$초라고 하자. 매 초가 시작될 때 먼저 모든 박테리아의 위치를 확인한다. 이때 모든 박테리아가 덫이 설치된 칸에 함께 있으면 그 즉시 모두 덫에 걸려 죽고, 그 시각이 답이 된다. 그렇지 않으면 모든 박테리아가 위 $1$~$4$번 동작을 동시에 한 번씩 수행한 뒤 다음 초로 넘어간다.

모든 박테리아가 죽는 시각을 초 단위로 구하는 프로그램을 작성하시오.

첫째 줄에 $N$, $M$, $K$가 주어진다. ($3 \le N, M \le 50$, $1 \le K \le 5$)

둘째 줄에 덫이 설치된 칸의 행 번호와 열 번호가 주어진다.

그다음 $1$번 박테리아부터 $K$번 박테리아까지 차례대로 정보가 주어진다. 각 박테리아의 정보는 두 부분으로 이루어진다.

• 첫 줄: 시작 칸의 행 $X_i$, 열 $Y_i$와 바라보는 방향 $C_i$가 주어진다. $C_i$는 위쪽 U, 오른쪽 R, 아래쪽 D, 왼쪽 L 중 하나이다.
• 다음 $N$개의 줄: $N \times M$ 크기의 행렬이 주어진다. 각 원소는 $0$부터 $9$까지의 숫자이며, 박테리아 $i$가 칸 $(x, y)$에 있을 때 읽는 숫자 $X$를 뜻한다.

모든 박테리아가 죽는 시각을 초 단위로 첫째 줄에 출력한다. 박테리아가 영원히 모두 죽지 않는다면 $-1$을 출력한다.