题目描述

农夫 John 曾经在他牧场的地面上画了一个矩形网格。在每个单元格中，他画了一个 $\texttt{+}$ 或一个 $\texttt{-}$（分别代表 $+1$ 和 $−1$）。

随着时间的推移，颜料褪色了，农夫 John 现在只记得某些单元格的值。然而，农夫 John 记得关于原始绘画的一个重要事实：

在每一行和每一列中，任意连续子段内的值之和总是在 $−1$ 到 $2$ 之间（含端点）。

举个例子，考虑行 $\texttt{+ - - +}$。它不满足条件，因为子段 $\texttt{+ [ - - ] +}$ 的和是 $-2$。

但是，行 $\texttt{- + + -}$ 确实满足条件。

[ - ] + + -    和 = -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$。

输出格式

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

2
1 3 3
+ 1 3
+ 1 1
- 1 2
1 3 3
+ 1 1
+ 1 3
+ 1 2

1
0

1
2 2 0

7

提示

以下是七个网格：

++
++

++
+-

++
-+

+-
++

+-
-+

-+
++

-+
+-

---

• 输入 $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 完成