题目描述

Farmer John 曾经在牧场地面上画了一个 \(R \times C\) 的矩形网格。每个格子里都写着一个符号：

• +，表示数值 \(+1\)
• -，表示数值 \(-1\)

随着时间流逝，颜料褪色了。现在 Farmer John 只记得其中一部分格子的符号，但他还记得原网格一定满足下面这个性质：

• 对于每一行和每一列，任意连续子段的元素和都在 \([-1,2]\) 范围内

例如，行

+ - - +

就不合法，因为中间那一段 - - 的和为 \(-2\)。

而下面这一行是合法的：

- + + -

它所有连续子段的和分别为：

[ - ] + + -    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)\)
• 接下来 \(X\) 行，每行给出一个字符 \(v \in \{+,-\}\) 和两个整数 \(r,c\)

表示第 \(r\) 行第 \(c\) 列的格子符号就是 \(v\)。

保证同一组测试中不会重复给出同一个格子。

另外保证：

• 所有测试中 \(R\) 的总和不超过 \(10^6\)
• 所有测试中 \(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
0

样例 2

输入

1
2 2 0

输出

7

说明

合法的 \(2 \times 2\) 网格共有七个：

+    ++    ++    +-    +-    -+    -+
+    +-    -+    ++    -+    ++    +-

数据范围

• 输入 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：无额外限制

命题信息

原题命题：Alex Chen