Pluses and Minuses
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.
Here are the seven grids:
++ ++ ++ +- ++ -+ +- ++ +- -+ -+ ++ -+ +-
SCORING:
- Inputs 3-4: min(R,C)=1 for 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
Source: USA Computing Olympiad.
Input Format
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
For each test, output the number of grids on a separate line.