문제

Luka는 또 화학 수업 시간에 지루함을 느끼고 있다.

이번에는 지능형 박테리아들을 가지고 놀고 있다.

그는 N행 M열의 직사각형 격자판 위에 K마리의 박테리아를 배치했다.

행은 위에서부터 1번부터 N번까지, 열은 왼쪽부터 1번부터 M번까지 번호가 매겨져 있다.

각 박테리아는 특정 칸에서 시작하며, 상하좌우 네 방향 중 하나를 바라보고 있다.

각 박테리아는 매 초마다 다음 행동을 순서대로 수행한다.

1. 현재 칸에 적혀 있는, 자기 전용 숫자 X를 읽는다.

2. 시계 방향으로 90도 회전을 X번 수행한다.

3. 바라보는 방향의 다음 칸이 격자판 밖이라면, 방향을 180도 반전시킨다.

4. 현재 바라보고 있는 방향의 칸으로 한 칸 이동한다.

Luka는 한 칸에 함정을 설치했다.

모든 박테리아가 같은 초에 동시에 그 칸에 도착하면, 함정이 작동하여 모든 박테리아가 죽는다.

화학 수업은 오늘 2시간밖에 남지 않았기 때문에, 게임이 몇 초 동안 지속되는지 구하여라.

입력

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

둘째 줄에 함정의 위치 X, Y가 주어진다. 이는 함정이 설치된 행과 열을 의미한다.

이후 각 박테리아 i에 대해 다음 정보가 주어진다.

• 두 정수 Xi, Yi 와 문자 Ci

  • Xi, Yi 는 박테리아의 시작 위치
  • Ci 는 시작 방향
    • U : 위
    • R : 오른쪽
    • D : 아래
    • L : 왼쪽

• 이어서 N행 M열의 숫자 격자가 주어진다. 각 칸의 숫자는 0 이상 9 이하이며, (x, y)의 숫자는 박테리아 i가 해당 칸에서 읽는 값을 의미한다.

출력

게임이 끝날 때까지 걸리는 시간을 초 단위로 출력한다.

만약 게임이 절대 끝나지 않는다면 -1을 출력한다.

예제 입력 1

3 3 1
2 2
1 1 R
010
000
000

예제 출력 1

3

예제 입력 2

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

예제 출력 2

8

예제 입력 3

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

예제 출력 3

296