Enjoy Collisions

Time Limit: 10 Seconds Memory Limit: 32768 KB

Given a rectangular area of size N by M which is partitioned into N*M unit squares(N columns and M rows). The four sides of the area are closed by walls (shown by the grey units in Figure 1). The coordinates of the lower-left corner unit are defined to be (1,1), and those of the upper-right corner (N,M). Inside the area there are some pillars (shown by the small blue squares in Figure 1) fixed which can be inserted into some block.

A block is either a square (denoted by (S, a) where a is the length of the side of square) or an isoceles right triangle (denoted by (T, a, style) where a is the length of its right angle's side, and style is its position). Every block has a hole which can fit a pillar in. The hole is positioned at the upper-left corner of a square block, and at the corner of the right angle of a triangle block (shown by the figures below).
Once a block fits into a pillar, it will be fixed by the pillar and can NOT move or be turned over or be rotated.

Now suppose that there is a small car (occupying 1 unit, and being represented by the red unit in Figure 1) moving from (1,1) to the upper-right corner. Whenever the car encounters a block or the wall, its moving direction will be changed. The car can only move to four directions: upper-right, lower-right, upper-left, and lower-left. When the car (red unit) moves to the upper-right direction, we have the following possible situations shown by the figures (1)-(8) (block and wall are represented by green units and a white unit is free of any barrier):
(1) upper-right turns to lower-right; (2) upper-right turns to upper-left;
(3) upper-right turns to lower-left; (4) upper-right turns to lower-right;
(5) upper-right turns to upper-left; (6) upper-right turns to lower-left;
(7) upper-right turns to lower-left; (8) continue moving to upper-right
Other cases can be deduced from the above 8 cases.

Given B pillars and B blocks, you are supposed to fix all the blocks into the area by fitting each one into a pillar. The blocks must NOT overlap each other or cross the walls. The question is that how many different ways of fixing the blocks that will guarantee the car moving back to (1,1) after finitely many steps?
The figure below shows an example of 2 blocks and 2 pillars. The numbers mark the sequential steps the car moves, and in this figure the car can indeed be back to (1,1). The 2 blocks are (s,2) and (s,1). The positions of the 2 pillars are (2,5) and (5,2).

Notice:
In case that the car can not move at all (example shown by the following figure), the fixing of the block is considered invalid.
Also note that the initial position of the car, (1,1), must NOT be occupied by any block.

Input

The first line of input contains an integer t (1<=t<=10), followed by t test cases.
The first line of each test case contains three integers N, M, and B, where 3<=N<=50, 3<=M<=50, and 1<=B<=10.
The next B lines of input are in the form of either
S sa
or
T ta style
indicating the kinds of B blocks. Here 1<=sa<=10, 2<=ta<=10, 1<=style<=4.
The next B lines give the B distinct coordinates of the pillars, in the form of
xi yi
where 1<=xi<=n and 1<=yi<=m.

Output

For each test case, output an integer which is the number of different ways of fixing the blocks such that the car can move back to (1,1).

Sample Input

Sample Output

1
0

Submit

Source: Zhejiang University Local Contest 2002