Amazing Robots

You control two robots, each placed in its own rectangular maze. In a maze, square (1, 1) is the top-left (north-west) corner. Maze $i$ ($i = 1, 2$) contains $G_i$ guards ($0 \le G_i \le 10$) that patrol back and forth along a straight line, trying to capture the robots. Your goal is to guide both robots out of their mazes without either one being captured.

At the start of each minute you broadcast a single command -- one of the four directions north, south, east, or west -- to both robots at once. Each robot tries to move one square in the commanded direction. If that square is a wall, the robot stays in place for that minute. If the move would take the robot off the edge of the maze, the robot exits the maze. Once a robot has exited, it ignores all further commands.

Guards move at the same instant as the robots, one square per minute. A guard starts on a given square facing a given direction and walks forward until it has advanced $P - 1$ squares, where $P$ is the number of squares in its patrol path. It then turns around instantly, walks back to its starting square, turns around again, and repeats this back-and-forth until both robots have exited. A guard never walks through a wall or off the maze, and no two guards ever collide or swap squares. No guard starts on a robot's square.

A guard captures a robot if, at the end of a minute, the guard and the robot occupy the same square, or if during the minute the guard and the robot swap squares (the guard moves into the robot's previous square while the robot moves into the guard's previous square). A robot can be captured only by guards in its own maze. A robot that has left its maze can no longer be captured.

Each maze is at most $20 \times 20$. Given the layout of both mazes, the starting square of each robot, and the patrol paths of the guards, find the minimum time needed for both robots to exit their mazes (the exit time of the later robot) while guiding them so that neither robot is ever captured. If it is impossible to get both robots out safely, report that instead.

The input describes the first maze and its guards, followed by the second maze and its guards in the same format.

For each maze:

• One line with two integers $R$ and $C$ -- the number of rows and columns ($1 \le R, C \le 20$).
• $R$ lines of exactly $C$ characters describing the layout. X marks the robot's starting square, . an open square, and # a wall. Each maze contains exactly one X.
• One line with an integer $G$ -- the number of guards ($0 \le G \le 10$).
• $G$ lines, each describing one guard as r c P d: the guard starts on square $(r, c)$, its patrol path is $P$ squares long ($2 \le P \le 4$), and it initially faces direction $d$, one of N, S, E, W.

Print a single integer: the minimum number of minutes after which both robots have exited their mazes -- that is, the smallest possible exit time of the later robot, taken over all command sequences that never let a robot be captured. If no such command sequence exists, print -1 instead. (When a solution exists, this value is at most 10000.)