Recently, some highly fertile mice have been rampant in the sewers, and the Anti-Rat Task Force is planning to eliminate them. The sewer system only contains pipes in the East-West and North-South directions, as shown in the figure.

The members of the Anti-Rat Task Force possess powerful weapons. They will place weapons at certain locations $(x, y)$ at certain times $t$. The weapons they use include:

1. Powerful Bomb: Its attack range is limited to the interior of the pipes, covering an area along the vertical and horizontal directions within a distance of $L$ from $(x, y)$, but it cannot penetrate the sewer walls. It explodes immediately after being placed, and all mice within the attack range are killed.
2. Mysterious Ray: Its attack range is a circle centered at $(x, y)$ with radius $R$, and it can penetrate sewer walls. After the ray is cast at time $t$, all mice within the attack range immediately fall into a coma, lose consciousness, and stop all physiological activities, only recovering at time $t+3$ (maintaining the orientation they had before losing consciousness). If a mouse is attacked by a ray again while in a coma, its recovery time is delayed by another 3 time units. For example, if a mouse is attacked by a ray at time $t$ and time $t+1$, it will remain in a coma until time $t+3+3$ before regaining consciousness. After regaining consciousness, the mouse continues its previous physiological activities.
3. Timed Bomb: Its attack range only includes $(x, y)$. After being placed at time $t$, it will explode at time $t+3$, and all mice at point $(x, y)$ at the time of the explosion will be killed.
4. Biological Bomb: Its attack range only includes $(x, y)$. It explodes immediately after being placed, causing the gender of all mice at point $(x, y)$ to change (regardless of age, female becomes male, male becomes female), but it does not affect the normal physiological activities of the mice.

Although the task force is powerful, the strength of the mice should not be underestimated.

We define one time unit as the interval between two adjacent moments. Starting from $t=0$, each mouse moves from its initial position in an initial direction. As long as there is a pipe in front, such as reaching point $A$ along direction $N$ in the figure above, the mouse will continue to move forward at a speed of 1. Otherwise, if there are pipes only on the left or only on the right, such as reaching point $B$ along direction $E$ in the figure above, and it cannot continue moving in the original direction, it will spend one time unit rotating 90 degrees in place in that direction, i.e., it will change its orientation to $S$. If there are pipes on both its left and right, such as reaching point $C$ along direction $W$ in the figure above, the mouse will recall how many times it has been in this situation. If it is the $k$-th time (where $k$ is odd), it will turn left; if $k$ is even, it will turn right. If it is at the end of a dead end, such as reaching point $D$ along direction $W$ in the figure above, it will spend two time units rotating 90 degrees to the right twice, i.e., it will change its orientation to $E$.

If at time $t$ there are exactly two mice at a certain point, one adult male and one adult female, they will stay at that point for two time units to breed. At time $t+2$, they will produce one baby mouse at that point for each direction that has a pipe, with baby males in the North-South directions and baby females in the East-West directions. For example, at point $C$ in the figure, if there are exactly two mice at time $t$ that are both adults and of opposite genders, then at time $t+2$, three baby mice will be born at that point, facing $N$, $S$, and $E$ respectively, with genders male, male, and female. Baby mice start moving immediately upon birth, while adult mice need to rest for one more time unit, i.e., they continue their activities at time $t+3$ (both mice maintain the orientation they had before breeding). Baby mice need 5 time units to grow into adult mice.

The task force has now formulated a rat extermination plan, which includes the locations, times, and types of weapons placed in the sewer pipes. You need to help them calculate the effect of the extermination operation. If the number of mice exceeds a certain limit during the implementation of the plan, a plague will break out.

Input

The first line contains 4 integers $L, R, m, n$ ($0 \le L, R \le 10, 1 \le m, n \le 50$), where $L$ represents the effective attack distance of the powerful bomb, $R$ represents the action radius of the mysterious ray, and $m$ and $n$ represent the scale of the sewer floor plan. The $x$-coordinate range is $[1, m]$, and the $y$-coordinate range is $[1, n]$.

From the 2nd line to the $(m+1)$-th line is the sewer structure map. We use the direction number 1 for $N$ (North), 2 for $E$ (East), 4 for $S$ (South), and 8 for $W$ (West). The $j$-th number $c_{i,j}$ in the $(i+1)$-th line represents the sum of all direction numbers connected by pipes at point $(i, j)$. For example, the sum of direction numbers at point $B$ in the figure above is 12.

The $(m+2)$-th line contains an integer $K$ ($1 \le K \le 50$), representing the number of mice at time 0 (at this time, all mice are adults).

From the $(m+3)$-th line to the $(m+K+2)$-th line, each line describes a mouse, including its initial coordinates $(x, y)$ ($1 \le x \le m, 1 \le y \le n$), orientation ('E', 'S', 'W', 'N'), and gender ('X' = male, 'Y' = female). The input guarantees that every mouse is inside a pipe.

The $(m+K+3)$-th line contains two integers $P, Limit$ ($1 \le P, Limit \le 100$), representing the number of weapons the task force is prepared to use and the limit on the number of mice for a plague to occur, respectively.

From the $(m+K+4)$-th line to the $(m+K+P+3)$-th line, each line describes a weapon, including its type (1-Powerful Bomb, 2-Mysterious Ray, 3-Timed Bomb, 4-Biological Bomb), the time $t$ it is placed ($t \ge 1$), and the coordinates $(x, y)$ ($1 \le x \le m, 1 \le y \le n$). The input guarantees that the weapons are placed inside pipes. The weapons are sorted in non-descending order of their placement time.

The last line contains an integer $Time$ ($1 \le Time \le 1000$), representing the end time of the simulation. $Time$ is guaranteed to be greater than the placement time of all weapons.

Output

The output contains a single integer. If a plague breaks out, the integer is -1; otherwise, it is the number of mice at time $Time$.

Examples

Input 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

Output 1

1

Note 1

The situation of each mouse at each time is shown in the table below:

The number of mice does not change after this, so there is still only 1 mouse at time 10.

Input 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

Output 2

73