문제

지안이는 예전에 마당의 격자판에 $+1$을 뜻하는 + 또는 $-1$을 뜻하는 -를 하나씩 그려 넣었다.

시간이 흘러 색이 바랬고, 지안이는 이제 일부 칸의 값만 기억한다. 하지만 지안이는 원래 격자판에 대해 다음과 같은 한 가지 중요한 사실을 기억하고 있다.

모든 행과 모든 열에 대해, 임의의 연속된 부분 구간의 합은 항상 $-1$ 이상 $2$ 이하($-1 \le \text{합} \le 2$)였다.

예를 들어, 어떤 행의 값이 + - - +인 경우를 생각해보자. 이 경우 부분 구간 + [ - - ] +의 합이 $-2$이므로 조건을 만족하지 않는다.

반면, 행의 값이 - + + -인 경우에는 다음과 같이 조건을 만족한다.

• [ - ] + + - 합 = $-1$
• [ - + ] + - 합 = $0$
• [ - + + ] - 합 = $+1$
• [ - + + - ] 합 = $0$
• - [ + ] + - 합 = $+1$
• - [ + + ] - 합 = $+2$
• - [ + + - ] 합 = $+1$
• - + [ + ] - 합 = $+1$
• - + [ + - ] 합 = $0$
• - + + [ - ] 합 = $-1$

지안이의 기억과 일치하는 서로 다른 격자판의 개수를 구하시오.

입력

첫째 줄에 독립적인 테스트 케이스의 개수 $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, R \times C)$)

이어지는 $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 R \times C \le 10^6$
• 테스트 케이스 15-22: 추가적인 제약 조건 없음.