Farmer John once painted a rectangular grid on the ground of his pasture. In each cell, he painted either a + or a −(representing +1 and −1, respectively).
Over time, the paint faded, and Farmer John now remembers the values of only some cells. However, Farmer John does remember one important fact about the original painting:
In every row and every column, the sum of the values in any contiguous subsegment was always between −1 and 2 (inclusive).
As an example, consider the row + - - +. It does not satisfy the condition, since the subsegment + [ - - ] + has sum −2.
However, the row - + + -does satisfy the condition.
[ - ] + + - sum = -1
[ - + ] + - sum = 0
[ - + + ] - sum = +1
[ - + + - ] sum = 0
- [ + ] + - sum = +1
- [ + + ] - sum = +2
- [ + + - ] sum = +1
- + [ + ] - sum = +1
- + [ + - ] sum = 0
- + + [ - ] sum = -1
Count the number of different grids consistent with Farmer John's memory.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains T(1≤T≤100), the number of independent tests. Each test is specified as follows:
The first line contains R, C, and X (1≤R,C≤5⋅105, 0≤X≤min(105,RC)), meaning that the grid has dimensions R×C and Farmer John remembers the values of X
different cells in the grid.
Then following X lines each contain a character v∈{+,−} followed by two integers r and c (1≤ r ≤R, 1≤ c ≤ C), meaning that the value at the rth row and cth column of the grid is v. It is guaranteed that no ordered pair (r,c) appears more than once within a single test.
Additionally, it is guaranteed that neither the sum of R nor the sum of C over all tests exceeds 106, and that the sum of X over all tests does not exceed 2⋅105.
OUTPUT FORMAT (print output to the terminal / stdout):
For each test, output the number of grids on a separate line.
SAMPLE INPUT:
2
1 3 3
+ 1 3
+ 1 1
- 1 2
1 3 3
+ 1 1
+ 1 3
+ 1 2
SAMPLE OUTPUT:
1
0
SAMPLE INPUT:
1
2 2 0
SAMPLE OUTPUT:
7
Here are the seven grids:
++ ++ ++ +- ++ -+ +- ++ +- -+ -+ ++ -+ +-
SCORING:
Inputs 3-4: min(R,C)=1for all tests
Inputs 5-6: R,C≤10 for all tests
Inputs 7-11: ∑max(R,C)2≤106
Inputs 12-14: ∑RC≤106
Inputs 15-22: No additional constraints.
Problem credits: Alex Chen
, respectively.
