[COCI2012-2013#6] BAKTERIJE

题目描述

一个 $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$。

输入输出样例

输入样例 #1

输出样例 #1

输入样例 #2

输出样例 #2

输入样例 #3

输出样例 #3

说明

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