Bacteria

There is an experiment board divided into $N$ rows and $M$ columns. The topmost row is row $1$ and the bottom row is row $N$; the leftmost column is column $1$ and the rightmost column is column $M$.

$K$ intelligent bacteria are placed on the board. Each bacterium starts on an assigned cell and faces one of four directions: up, down, left, or right. Every second, each bacterium performs the following steps once, in order:

1. Read the number $X$ written on its current cell. This number differs from bacterium to bacterium, and each bacterium reads the number that belongs to it.
2. Rotate clockwise by $90^\circ$, $X$ times.
3. If the cell it now faces lies outside the board, rotate $180^\circ$.
4. Move one cell forward in the direction it faces.

One cell of the board holds a trap. Call the initial placement of the bacteria second $1$. At the start of every second, the positions of all bacteria are checked first. If all bacteria are on the trap cell together, they are immediately caught and die, and that second is the answer. Otherwise every bacterium performs steps $1$-$4$ once simultaneously, and time advances to the next second.

Write a program that finds, in seconds, when all bacteria die.

The first line contains $N$, $M$, and $K$. ($3 \le N, M \le 50$, $1 \le K \le 5$)

The second line contains the row and column of the trap cell.

Then the descriptions of bacteria $1$ through $K$ follow in order. Each description has two parts:

• One line with the starting cell's row $X_i$, column $Y_i$, and facing direction $C_i$. $C_i$ is one of up U, right R, down D, or left L.
• The next $N$ lines give an $N \times M$ matrix. Each element is a digit from $0$ to $9$ and denotes the number $X$ that bacterium $i$ reads when it is on cell $(x, y)$.

Print, on the first line, the second at which all bacteria die. If the bacteria never all die, print $-1$.