Migrated from Lutece 569 Color II

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

ZT loves to paint on papers. One day, he wants to paint every cell on the board whose size is $N \times M$ with black and white. However, the painted board should meet this condition: for every $2 \times 2$ block, there are exactly $W$ white cells and $4 - W$ black cells. To make this problem more interesting, some cells on board have already been colored. How many different boards can ZT paint?

Note that two boards are different if at least one corresponding cell's color is different.

Input

There are multiple test cases. The first line of the input will be an integer $T$ ($T\leq 50$) indicating the number of test cases.

For each test case there are three integers $N$, $M$, $K$ ($2 \leq N, M \leq 100000$, $0 \leq K \leq 100000$) in a single line, representing the size of board and the number of colored cells. For the following $K$ lines, each line contains two integers $R_i$, $C_i$ and a character $S_i$. It means the cell in the $R_i^{th}$ row and $C_i^{th}$ column has been colored in $S_i$. $1 \leq R_i \leq N$, $1 \leq C_i \leq M$, $S_i$ is W or B indicating this cell is colored in white or black.

Output

For each test case, print Case #t: first, in which $t$ is the number of the test case starting from $1$. Then output five integers indicating the number of different colored boards when $W = 0, W = 1, W = 2, W = 3, W = 4$. The result should be modulo by $20120407$.

Samples

1
3 3 2
1 1 B
2 2 W

Case #1: 0 1 4 3 0

Note

The first sample is like this

B..
.W.
...

Resources

10th UESTC Programming Contest Final