Description

There is a rectangular area with $N$ rows and $M$ columns. Rows are numbered from $1$ to $N$ from top to bottom, and columns are numbered from $1$ to $M$ from left to right. There are $K$ bacteria placed in these cells. Each bacterium has its own direction and movement rules.

The rules are as follows: it reads the digit $X$ in its current cell, then turns clockwise by $90^{\circ}$ exactly $X$ times. If it is facing the boundary of the rectangle, it turns $180^{\circ}$. Finally, it moves into the cell it is facing.

We place a trap in one cell. When all bacteria enter the trap at the same time, the trap is activated, and the bacteria will be destroyed within one second.

Given all information, determine when all bacteria are destroyed.

Input Format

The first line contains three positive integers $N, M, K$.

The next line contains two integers $x, y$, meaning there is a trap at row $x$, column $y$.

Then each bacterium is described in order:

• First, one line contains two integers $X, Y$ and one letter $C$, representing its row and column coordinates and its direction. U means up, D means down, L means left, and R means right.
• Next is a matrix giving the value $X$ for this bacterium in every cell, with $0\leq X\leq 9$.

Output Format

Output one integer on one line: the last time when the bacteria are killed. If it is impossible to destroy all of them, output $-1$.

3 3 1
2 2
1 1 R
010
000
000

3

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

8

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

296

Hint

Constraints: $3\leq N\leq 50$, $3\leq M \leq 50$, $1\leq K\leq 5$.

Translated by ChatGPT 5