C0158 [CTSC2002Day2-B]灭鼠行动

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

灭鼠特工队的队员拥有强大的武器。他们将在某些时刻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$ 时刻开始，每只老鼠就从初始位置向某一初始方向运动。只要前方有管道，如上图中沿方向 N 到达点 A，老鼠就会一直向前走，运动速度为 $1$。否则，如果只有左边或者只有右边有管道，如上图中沿方向 E 到达点 B 时，再不能沿原方向继续前进，它就会花费一个时间单位朝该方向原地转动 $90$ 度，即它将改变方向朝向 S。如果它左边和右边都有管道，如上图中沿方向 W 到达点 C，老鼠会回忆这是第几次处于这种情况。如果是第奇数次遇到，它会向左转，第偶数次就向右转。如果它处于一条死路的尽头，如上图中沿方向 W 到达点 D，那么它会花费两个时间单位连续向右转两次，即它将改变方向朝向 E。

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

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

样例输入 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

样例输入 2

2 3 5 6
6 10 14 10 14 12
5 0 5 0 3 13
3 10 9 0 0 5
0 0 0 0 0 5
0 0 0 0 2 9
4
3 1 N X
3 2 E Y
2 6 S Y
1 5 W X
3 80
1 1 1 4
1 21 2 6
1 41 5 6
80

样例输出 2

73