题目背景

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

题目描述

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

输入格式

第一行三个正整数 接下来一行，两个数$x,y$表示在$x$行$y$列处有一个陷井。 接下来依次描述每一个细菌。 首先是一行两个数$X,Y$ 和一个字母$C$，分别表示行列坐标和它的方向，$U$表示上， $D$表示下，$L$表示左，$R$表示右。 接下来一个矩阵，表示这个细菌在这个每一个单元格上的$X$，$0≤X≤9$

输出格式

一行一个数，表示细菌被杀死的最后时间，如果无法全部消灭则输出$-1$。

样例 #1

样例输入 #1

3 3 1
2 2
1 1 R
010
000
000

样例输出 #1

3

样例 #2

样例输入 #2

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

样例输出 #2

8

样例 #3

样例输入 #3

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

样例输出 #3

296

提示

$N(3≤N≤50),M(3≤M≤50),K(1≤K≤5)$