[CTSC2002] 灭鼠行动

题目描述

最近，有一些繁殖力很强的老鼠在下水道非常猖獗，灭鼠特工队正在计划消灭这些老鼠。下水道只有东西方向和南北方向的管道，如图所示。

灭鼠特工队的队员拥有强大的武器。他们将在某些时刻 $t$ 在某些位置 $(x,y)$ 放置武器。他们所使用的武器包括：

1. 强力炸弹：它的攻击范围限定在管道内部，是沿竖直和水平方向，离 $(x,y)$ 的距离不超过 $L$ 的区域，但是不能穿透下水道壁。它将在放置之后立刻爆炸，且攻击范围内的老鼠将被全部炸死。

2. 神秘射线：它的攻击范围是以 $(x,y)$ 为圆心，半径为 $R$ 的圆，而且可以穿透下水道壁。射线在时刻 $t$ 施放后，将使攻击范围内的所有老鼠立刻陷入昏迷状态，失去知觉，停止一切生理活动，待到第 $t+3$ 时刻才能恢复（保持失去知觉前的朝向）。如果在昏迷状态中再次受到射线攻击，那么它将再推迟 $3$ 个时刻恢复。例如，若老鼠在时刻 $t$ 和时刻 $t+1$ 个受到一次射线的攻击，则它要昏迷到第 $t+3+3$ 时刻才能恢复知觉。恢复知觉以后，老鼠将继续以前的生理活动。

3. 定时炸弹：它的攻击范围仅包括 $(x,y)$。它在时刻 $t$放置后，将在第 $t+3$ 时刻爆炸，爆炸时处在 $(x,y)$ 点的老鼠将全部被炸死。

4. 生物炸弹：它的攻击范围仅包括 $(x,y)$。它将在放置之后立刻爆炸，使处在 $(x,y)$ 点的所有老鼠的性别改变（无论大小，雌变成雄，雄变成雌），但不影响老鼠的正常生理活动。

虽然特工队的实力很强，但是老鼠的实力也不容忽视。

我们定义，相邻两个时刻之间是一个时间单位。从 $t=0$ 时刻开始，每只老鼠就从初始位置向某一初始方向运动。只要前方有管道，如上图中沿方向 $\texttt{N}$ 到达点 $\texttt{A}$，老鼠就会一直向前走，运动速度为 $1$。否则，如果只有左边或者只有右边有管道，如上图中沿方向 $\texttt{E}$ 到达点 $\texttt{B}$ 时，再不能沿原方向继续前进，它就会花费一个时间单位朝该方向原地转动 $90$ 度，即它将改变方向朝向 $\texttt{S}$。如果它左边和右边都有管道，如上图中沿方向 $\texttt{W}$ 到达点 $\texttt{C}$，老鼠会回忆这是第几次处于这种情况。如果是第奇数次遇到，它会向左转，第偶数次就向右转。如果它处于一条死路的尽头，如上图中沿方向 $\texttt{W}$ 到达点 $\texttt{D}$，那么它会花费两个时间单位连续向右转两次，即它将改变方向朝向E。

如果在 $t$ 时刻某点恰好只有两只老鼠，一只为成年雄老鼠，一只为成年雌老鼠，则它们将会因为进行繁殖而在该点停留两个单位时间，$t+2$ 时刻会在该点对每个有管道的方向生出一只朝着该方向的小老鼠，南北方向为雄小老鼠，东西方向为雌小老鼠。如上图中的 $\texttt{C}$ 点，$t$ 时刻恰好只有两只老鼠，它们都已成年且性别相异，那么在第 $t+2$ 时刻就会在该点生出三只小老鼠，它们分别朝向 $\texttt{N}$、$\texttt{S}$、$\texttt{E}$，性别分别是雄性、雄性、雌性。小老鼠一出生就立刻开始移动，而成年老鼠需要再休息一个时间单位，即在 $t+3$ 时刻继续活动（两只老鼠都保持生育前的朝向）。小老鼠需要成长 $5$ 个时间单位才会长成为成年老鼠。

特工队现在制定了一套灭鼠计划，其中包括在下水管道放置武器的位置、时间和类型。你需要帮他们计算灭鼠行动的效果，如果在该计划实施的过程中，老鼠的数量超过了某个限定值，就会爆发鼠疫。

输入格式

第一行为 $4$ 个整数 $L, R, m, n(0\le L,R\le 10,1\le m,n\le 50)$，其中 $L$ 代表强力炸弹的有效攻击距离，$R$ 代表神秘射线的作用半径，$m$ 和 $n$ 代表下水道平面图的规模。$x$ 坐标的范围为 $[1,m]$, $y$ 坐标的范围为 $[1,n]$。

从第 $2$ 行到第 $m+1$ 行为下水道结构图。我们用方向数 $1$ 代表 $\texttt{N}$ (北)，用方向数 $2$ 代表$\texttt{E}$ (东)，用方向数 $4$ 代表 $\texttt{S}$ (南)，用方向数 $8$ 代表 $\texttt{W}$ (西)。第 $i+1$ 行的第 $j$ 个数字 $c_{i,j}$ 代表点 $(i,j)$ 处有管道连接的所有方向数之和，如上图中的点 $\texttt{B}$ 的方向数之和为 $12$。

第 $m+2$ 行为一个整数 $K（1\le K\le 50）$，代表时刻 $0$ 时老鼠的个数（此时老鼠都是成年的）。

第 $m+3$ 行到第 $m+K+2$ 行每行描述一只老鼠，包括该老鼠的初始坐标 $(x,y), (1\le x\le m, 1\le y\le n)$，朝向（’$\texttt{E}$’,’$\texttt{S}$’,’$\texttt{W}$’,’$\texttt{N}$’）以及性别（’$\texttt{X}$’=雄，’$\texttt{Y}$’=雌）。输入保证每个老鼠都在水管内。

第 $m+K+3$ 行为两个整数 $P，Limit(1\le P, Limit\le 100)$，分别表示特工队准备使用的武器个数以及控制鼠疫发生的老鼠数量的极限。

第 $m+K+4$ 行到第 $m+K+P+3$ 行每行描述一个武器，包括该武器的类型($1$-强力炸弹，$2$-神秘射线，$3$-定时炸弹，$4$-生物炸弹)，放置的时刻 $t(t\ge 1)$，放置的坐标 $(x,y) (1\le x\le m, 1\le y\le n)$，输入保证武器放置在管道内。武器按照放置的时间不降序排列。

最后一行包含一个整数 $Time(1\le Time\le 1000)$，表示模拟的结束时刻。$Time$ 保证比所有武器的放置时刻大。

输出格式

包含一个整数。如果爆发了鼠疫，该整数为 $-1$，否则该整数为时刻 $Time$ 的老鼠数目。

样例 #1

样例输入 #1

1 1 3 3
6 14 12
7 15 13
3 11 9
3
1 3 W X
1 2 W X
3 3 S X
3 100
1 1 2 2
3 1 3 1
2 2 3 2
10

样例输出 #1

1

提示

样例解释