P14985 [USACO26JAN1] Pluses and Minuses P

Farmer John once painted a rectangular grid on the ground of his pasture. In each cell, he painted either a $\texttt{+}$ or a $\texttt{-}$ (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 $\texttt{+ - - +}$. It does not satisfy the condition, since the subsegment $\texttt{+ [ - - ] +}$ has sum $-2$. However, the row $\texttt{- + + -}$ does satisfy the condition. ```none [ - ] + + - 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.

The first line contains $T$ ($1\le T\le 100$), the number of independent tests. Each test is specified as follows: The first line contains $R$, $C$, and $X$ ($1\le R,C\le 5\cdot 10^5$, $0\le X\le \min(10^5,RC)$), meaning that the grid has dimensions $R\times C$ and Farmer John remembers the values of $X$ different cells in the grid. Then following $X$ lines each contain a character $v\in \{\texttt{+}, \texttt{-}\}$ followed by two integers $r$ and $c$ ($1\le r\le R, 1\le c\le C$), meaning that the value at the $r$th row and $c$th 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 $10^6$, and that the sum of $X$ over all tests does not exceed $2\cdot 10^5$.

For each test, output the number of grids on a separate line.

Here are the seven grids: ```none ++ ++ ++ +- ++ -+ +- ++ +- -+ -+ ++ -+ +- ``` --- - Inputs 3-4: $\min(R,C)=1$ for all tests - Inputs 5-6: $R,C\le 10$ for all tests - Inputs 7-11: $\sum \max(R,C)^2 \le 10^6$ - Inputs 12-14: $\sum RC \le 10^6$ - Inputs 15-22: No additional constraints.