박테리아

지금은 화학 시간이다. 이번 시간에는 지능이 있는 박테리아를 연구하는 실험을 하고 있다. 상근이는 지루한 실험 대신 독특한 자신만의 실험을 하기로 했다.

먼저, 실험판을 N행 M열로 나눈다. 제일 윗 행은 1번, 마지막 행은 N번이고, 가장 왼쪽 열은 1번, 오른쪽은 M번 행이다. 그 다음 박테리아를 K마리 준비한다.

각 박테리아는 상근이가 지정한 칸에서 모험을 시작하게 되며, 위, 아래, 오른쪽 왼쪽 중 한 방향을 바라보고 있다. 각 박테리아는 일초동안 아래와 같은 일을 수행한다.

1. 박테리아가 현재 있는 칸에 쓰여 있는 숫자 X를 읽는다. 이 숫자는 박테리아마다 다르며, 지능이 있는 박테리아이기 때문에 자신에게 해당하는 숫자를 읽을 수 있다.
2. 시계방향으로 X번 90도 회전을 한다.
3. 만약 바라보고 있는 방향에 있는 칸이 실험판의 경계를 넘어간다면, 180도 회전을 한다.
4. 바라보고 있는 칸으로 한 칸 움직인다.

상근이는 한 칸에 덫을 설치해 놓았다. 모든 박테리아가 덫이 있는 칸으로 동시에 이동하면, 즉시 덫에 걸려 죽게 된다.

모든 박테리아가 죽는데 몇 초가 걸리는지 구하는 프로그램을 작성하시오.

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

다음 줄에는 덫이 설치된 곳의 행 X와 열 Y가 주어진다.

나머지 줄은 박테리아에 대한 설명이며, 1번 박테리아부터 K번까지 순서대로 주어진다.

첫 줄에는 박테리아의 시작 위치 Xi Yi와 바라보고 있는 방향 Ci가 주어진다. (Ci = U(위), R(오른쪽), D(아래), L(왼쪽))

그 다음 줄에는 N × M 크기의 행렬이 주어진다. 행렬을 구성하는 원소는 0과 9를 포함하는 사이의 숫자이며, 박테리아 i아 (x,y)를 방문했을 때 해당하는 X이다.

첫째 줄에 모든 박테리아가 죽는데 걸리는 시간을 출력한다. (단위: 초) 만약, 박테리아가 모두 죽지 않는다면, -1을 출력한다.