Illusive Chase

Time limit1sMemory limit128 MB

Summary

Given a grid with obstacles and a log of chase trips, each recorded as a range of steps in one direction, count the possible starting cells consistent with the whole sequence.

Level: Medium7 of 10
Topics: Array, Brute force, Simulation, Implementation
Solved: No attempts yet

Problem

Tom the robocat is on show at a Robotics Exhibition for an enthusiastic audience of youngsters, placed on an $m \times n$ field. Tom, which is switched off at first, is placed on some arbitrary cell of the field by a volunteer from the audience. At time zero of the show, Tom is switched on by a remote control.

Tom is shown a holographic illusion of Jerry a short distance away, such that the straight path between them is always either vertical or horizontal and contains no obstacles. Tom tries to reach Jerry, but the instant he arrives, the illusion moves elsewhere and the chase continues. Let us call each chase in a single direction (up, down, left, or right) a chase trip. Each trip starts where the previous illusion stood and ends where the next illusion appears. After a number of chase trips, the illusion stops appearing, and Tom wonders what to do next. At this moment he is told that, for sure, if he returns to the cell where he began the chase, a real Jerry is sleeping there and he can catch it.

To simplify the problem, treat the field as a grid of square cells. Some cells are occupied by obstacles. At any instant Tom stands on an empty cell and so does Jerry (the illusion), with a straight horizontal or vertical path between them. Each time Tom is shown an illusion, he can reach it by moving in only one of the four directions without bumping into an obstacle. Tom moves to an adjacent cell by taking exactly one step.

The catch is that Tom's logging mechanism is a little fuzzy, so the number of steps he took on each chase trip is recorded as an interval of integers (for example, 2 to 5 steps to the left). Your task is to send a program to Tom's memory to help him get back. To make the task easier for this contest, your program only has to count all the cells from which he might have started the chase.

Input

The first line of the input contains a single integer $t$ ( $1 \le t \le 10$ ), the number of test cases, followed by the input data for each test case. The first line of each test case contains two integers $m$ and $n$ , the number of rows and columns of the grid respectively ( $1 \le m, n \le 100$ ). Then follow $m$ lines, each containing $n$ integers that are either 0 or 1, indicating whether the corresponding cell is empty (0) or occupied by an obstacle (1).

After the field description comes a sequence of lines, each describing one chase trip of Tom, in order. Each line contains two positive integers giving the inclusive range of steps Tom took, followed by a single upper-case character giving the direction of the trip: one of R (right), L (left), U (up), or D (down). (These directions are relative to the field and are not the direction Tom happens to face.) This part of the test case is terminated by a line containing exactly two zeros.

Output

For each test case, print a single line containing one integer: the number of cells from which Tom might have started the chase.

Examples4

Example 1

Input

2
6 6
0 0 0 0 0 0
0 0 0 1 1 0
0 1 0 0 0 0
0 0 0 1 0 0
0 0 0 1 0 1
0 0 0 0 0 1
1 2 R
1 2 D
1 1 R
0 0
3 4
0 0 0 0
0 0 0 0
0 0 0 0
1 2 R
3 7 U
0 0

Expected output

10
0

Example 2
Input
```
1
1 5
0 0 0 0 0
2 3 R
0 0
```
Expected output
```
3
```
Example 3
Input
```
1
1 5
0 0 0 0 0
2 3 L
0 0
```
Expected output
```
3
```
Example 4
Input
```
1
1 5
0 1 0 0 0
1 3 R
0 0
```
Expected output
```
2
```