놀라운 로봇

당신은 각자 다른 직사각형 미로에 놓인 로봇 두 대를 조종한다. 각 미로에서 칸 (1, 1)은 왼쪽 위(북서쪽) 모서리다. 미로 $i$ ($i = 1, 2$)에는 로봇을 잡으려고 직선 경로를 왕복하며 순찰하는 경비원이 $G_i$명 ($0 \le G_i \le 10$) 있다. 목표는 두 로봇을 모두 잡히지 않고 미로 밖으로 내보내는 것이다.

매 분이 시작될 때 당신은 네 방향(북, 남, 동, 서) 중 하나의 명령을 두 로봇에게 동시에 방송한다. 각 로봇은 명령받은 방향으로 한 칸 이동하려 한다. 그 칸이 벽이면 그 분 동안 제자리에 머무른다. 이동이 미로의 가장자리 밖으로 나가는 경우 로봇은 미로를 빠져나간다. 한 번 빠져나간 로봇은 이후의 모든 명령을 무시한다.

경비원은 로봇과 같은 순간에 매 분 한 칸씩 이동한다. 경비원은 주어진 칸에서 주어진 방향을 보고 출발해, 순찰 경로의 칸 수 $P$에 대해 앞으로 $P - 1$칸 전진한 뒤 즉시 방향을 바꿔 출발 칸으로 되돌아오고, 다시 방향을 바꾸는 왕복을 두 로봇이 모두 미로를 빠져나갈 때까지 반복한다. 경비원은 벽을 통과하거나 미로 밖으로 나가지 않으며, 두 경비원이 서로 충돌하거나 자리를 맞바꾸는 일도 없다. 어느 경비원도 로봇의 출발 칸에서 시작하지 않는다.

경비원은 어느 분이 끝났을 때 로봇과 같은 칸에 있거나, 그 분 동안 로봇과 자리를 맞바꾸면(경비원이 로봇의 직전 칸으로 이동하고 동시에 로봇이 경비원의 직전 칸으로 이동) 그 로봇을 잡는다. 각 로봇은 자신이 있는 미로의 경비원에게만 잡힐 수 있다. 미로를 벗어난 로봇은 더 이상 잡히지 않는다.

두 미로는 각각 최대 $20 \times 20$이다. 두 미로의 배치, 각 로봇의 출발 칸, 경비원들의 순찰 경로가 주어질 때, 어느 로봇도 잡히지 않도록 조종하여 두 로봇이 모두 미로를 빠져나가는 데 걸리는 최소 시간(나중에 빠져나가는 로봇의 탈출 시각)을 구하라. 두 로봇을 모두 안전하게 내보내는 것이 불가능하면 그 사실을 답하라.

입력은 먼저 첫 번째 미로와 그 경비원들을, 이어서 같은 형식으로 두 번째 미로와 그 경비원들을 기술한다.

각 미로마다:

• 두 정수 $R$과 $C$가 한 줄에 주어진다. 각각 행과 열의 수다 ($1 \le R, C \le 20$).
• 미로 배치를 나타내는, 정확히 $C$개의 문자로 이루어진 $R$개의 줄이 온다. X는 로봇의 출발 칸, .은 빈 칸, #은 벽을 뜻한다. 각 미로에는 X가 정확히 하나 있다.
• 경비원 수 $G$가 한 줄에 주어진다 ($0 \le G \le 10$).
• 각 경비원을 기술하는 $G$개의 줄이 온다. 각 줄은 r c P d 형식으로, 경비원은 칸 $(r, c)$에서 출발하고 순찰 경로의 길이는 $P$칸이며 ($2 \le P \le 4$) 처음에 방향 $d$를 향한다. $d$는 N, S, E, W 중 하나다.

정수 하나를 출력한다. 어느 로봇도 잡히지 않는 모든 명령 순서에 대해, 두 로봇이 모두 미로를 빠져나가는 시각(나중에 빠져나가는 로봇의 탈출 시각) 중 가능한 최솟값을 분 단위로 출력한다. 그러한 명령 순서가 존재하지 않으면 대신 -1을 출력한다. (해가 존재할 때 이 값은 최대 10000이다.)