P14985 [USACO26JAN1] Pluses and Minuses P

农夫 John 曾经在他牧场的地面上画了一个矩形网格。在每个单元格中，他画了一个 $\texttt{+}$ 或一个 $\texttt{-}$（分别代表 $+1$ 和 $−1$）。 随着时间的推移，颜料褪色了，农夫 John 现在只记得某些单元格的值。然而，农夫 John 记得关于原始绘画的一个重要事实： 在每一行和每一列中，任意连续子段内的值之和总是在 $−1$ 到 $2$ 之间（含端点）。 举个例子，考虑行 $\texttt{+ - - +}$。它不满足条件，因为子段 $\texttt{+ [ - - ] +}$ 的和是 $-2$。 但是，行 $\texttt{- + + -}$ 确实满足条件。 ```none [ - ] + + - 和 = -1 [ - + ] + - 和 = 0 [ - + + ] - 和 = +1 [ - + + - ] 和 = 0 - [ + ] + - 和 = +1 - [ + + ] - 和 = +2 - [ + + - ] 和 = +1 - + [ + ] - 和 = +1 - + [ + - ] 和 = 0 - + + [ - ] 和 = -1 ``` 计算与农夫 John 记忆相符的不同网格的数量。

第一行包含 $T$（$1\le T\le 100$），表示独立测试的数量。每个测试按以下格式指定： 第一行包含 $R$、$C$ 和 $X$（$1\le R,C\le 5\cdot 10^5$，$0\le X\le \min(10^5,RC)$），表示网格的尺寸为 $R\times C$，且农夫 John 记得网格中 $X$ 个不同单元格的值。 接下来的 $X$ 行，每行包含一个字符 $v\in \{\texttt{+}, \texttt{-}\}$ 和两个整数 $r$ 和 $c$（$1\le r\le R, 1\le c\le C$），表示网格第 $r$ 行第 $c$ 列的值为 $v$。保证在同一测试中，有序对 $(r,c)$ 不会出现多次。 此外，保证所有测试的 $R$ 之和与 $C$ 之和都不超过 $10^6$，且所有测试的 $X$ 之和不超过 $2\cdot 10^5$。

对于每个测试，将网格数量输出在单独一行。

以下是七个网格： ```none ++ ++ ++ +- ++ -+ +- ++ +- -+ -+ ++ -+ +- ``` --- - 输入 $3$-$4$：所有测试中 $\min(R,C)=1$ - 输入 $5$-$6$：所有测试中 $R,C\le 10$ - 输入 $7$-$11$：$\sum \max(R,C)^2 \le 10^6$ - 输入 $12$-$14$：$\sum RC \le 10^6$ - 输入 $15$-$22$：无额外约束。 翻译由 DeepSeek V3 完成