题目描述

一个 $N$ 行，$M$ 列的矩形区域，行从上到下从 $1$ 到 $N$ 编号，列从左到右从 $1$ 到 $M$ 编号，有 $K$ 个细菌被放在这些单元格内，每个细菌都有自己的方向和运动规则。规则如下：读取自己在这个单元格的数字 $X$，顺时针转 $90^{\circ}$ $X$ 次，如果它面对矩形边界，则转 $180^{\circ}$，最后进入自己面向的单元格。我们放置一个陷阱在某一单元格，当所有细菌同时进入陷阱时，陷阱被激活，细菌会在一秒内被消灭。

给定所有信息，求什么时候所有细菌被消灭。

输入格式

第一行三个正整数 $N, M, K$。

接下来一行，两个数 $x, y$ 表示在 $x$ 行 $y$ 列处有一个陷阱。

接下来依次描述每一个细菌：

• 首先是一行两个数 $X,Y$ 和一个字母 $C$，分别表示行列坐标和它的方向，U 表示上，D 表示下，L 表示左，R 表示右。
• 接下来一个矩阵，表示这个细菌在这个每一个单元格上的$X$，$0\leq X\leq 9$。

输出格式

一行一个数，表示细菌被杀死的最后时间，如果无法全部消灭则输出 $-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

提示

$3\leq N\leq 50$，$3\leq M \leq 50$，$1\leq K\leq 5$。