Farmer John 曾经在他的牧场地面上绘制了一个矩形网格。在每个单元格中，他涂上了一个 $+$ 或一个 $−$（分别代表 $+1$ 和 $−1$）。

随着时间的推移，油漆褪色了，Farmer John 现在只记得部分单元格的值。然而，Farmer John 确实记得关于原始画作的一个重要事实：

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

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

然而，行 $\texttt{- + + -}$ 满足该条件。

[ - ] + + -    sum = -1
[ - + ] + -    sum = 0
[ - + + ] -    sum = +1
[ - + + - ]    sum = 0
- [ + ] + -    sum = +1
- [ + + ] -    sum = +2
- [ + + - ]    sum = +1
- + [ + ] -    sum = +1
- + [ + - ]    sum = 0
- + + [ - ]    sum = -1

计算与 Farmer 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$，且 Farmer John 记得网格中 $X$ 个不同单元格的值。

接下来的 $X$ 行，每行包含一个字符 $v\in {+, -}$，后跟两个整数 $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$。

输出格式

对于每个测试用例，在单独的一行中输出网格的数量。

样例

输入样例 1

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

输出样例 1

1
0

输入样例 2

1
2 2 0

输出样例 2

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：无额外限制。