Nông dân John từng sơn một lưới hình chữ nhật trên mặt đất ở đồng cỏ của mình. Trong mỗi ô, ông sơn dấu \(+\) hoặc dấu \(-\) (lần lượt biểu diễn \(+1\) và \(-1\)).

Theo thời gian, lớp sơn phai dần, và giờ đây Nông dân John chỉ nhớ giá trị của một số ô. Tuy nhiên, Nông dân John vẫn nhớ một tính chất quan trọng của bức vẽ ban đầu:

Trong mỗi hàng và mỗi cột, tổng các giá trị của mọi đoạn con liên tiếp luôn nằm trong khoảng từ \(-1\) đến \(2\) (tính cả hai đầu).

Ví dụ, xét hàng \(\texttt{+ - - +}\). Hàng này không thỏa mãn điều kiện vì đoạn con \(\texttt{+ [ - - ] +}\) có tổng bằng \(-2\).

Ngược lại, hàng \(\texttt{- + + -}\) thỏa mãn điều kiện.

[ - ] + + -    tổng = -1
[ - + ] + -    tổng = 0
[ - + + ] -    tổng = +1
[ - + + - ]    tổng = 0

- [ + ] + -    tổng = +1
- [ + + ] -    tổng = +2
- [ + + - ]    tổng = +1
- + [ + ] -    tổng = +1
- + [ + - ]    tổng = 0
- + + [ - ]    tổng = -1

Hãy đếm số lưới khác nhau phù hợp với những gì Nông dân John nhớ.

Dữ liệu vào

Dòng đầu tiên chứa \(T\) (\(1\le T\le 100\)), là số bộ test độc lập. Mỗi bộ test được mô tả như sau:

Dòng đầu tiên chứa \(R\), \(C\) và \(X\) (\(1\le R,C\le 5\cdot 10^5\), \(0\le X\le \min(10^5,RC)\)), cho biết lưới có kích thước \(R\times C\) và Nông dân John nhớ giá trị của \(X\) ô khác nhau trong lưới.

\(X\) dòng tiếp theo, mỗi dòng chứa một ký tự \(v\in\{+,-\}\), theo sau là hai số nguyên \(r\) và \(c\) (\(1\le r\le R\), \(1\le c\le C\)), cho biết giá trị tại hàng thứ \(r\), cột thứ \(c\) của lưới là \(v\). Đảm bảo rằng không có cặp có thứ tự \((r,c)\) nào xuất hiện nhiều hơn một lần trong cùng một bộ test.

Ngoài ra, đảm bảo rằng cả tổng \(R\) lẫn tổng \(C\) trên tất cả các bộ test đều không vượt quá \(10^6\), và tổng \(X\) trên tất cả các bộ test không vượt quá \(2\cdot 10^5\).

Dữ liệu ra

Với mỗi bộ test, in số lưới trên một dòng riêng.

Ví dụ

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

++
++

++
+-

++
-+

+-
++

+-
-+

-+
++

-+
+-

Phân nhóm

• Các test 3–4: \(\min(R,C)=1\) đối với mọi bộ test.
• Các test 5–6: \(R,C\le 10\) đối với mọi bộ test.
• Các test 7–11: \(\sum \max(R,C)^2\le 10^6\).
• Các test 12–14: \(\sum RC\le 10^6\).
• Các test 15–22: Không có ràng buộc bổ sung.

Nguồn

USACO 2026 First Contest, Platinum Division — "Pluses and Minuses". Tác giả: Alex Chen. https://usaco.org/index.php?page=viewproblem2&cpid=1550