#8863
Subtask

Pluses and Minuses 1s 1024MB

Problems

Farmer John once painted a rectangular grid on the ground of his pasture. In each cell, he painted either a + or a − (representing +1 and −1, respectively).

Over time, the paint faded, and Farmer John now remembers the values of only some cells. However, Farmer John does remember one important fact about the original painting:

In every row and every column, the sum of the values in any contiguous subsegment was always between −1 and 2 (inclusive).

As an example, consider the row + - - +. It does not satisfy the condition, since the subsegment + [ - - ] + has sum −2.

However, the row - + + - does satisfy the condition.

[ - ] + + - sum = -1

[ - + ] + - sum = 0

[ - + + ] - sum = +1

[ - + + - ] sum = 0

- [ + ] + - sum = +1

- [ + + ] - sum = +2

- [ + + - ] sum = +1

- + [ + ] - sum = +1

- + [ + - ] sum = 0

- + + [ - ] sum = -1

Count the number of different grids consistent with Farmer John's memory.

Input

The first line contains T (1≤T≤100), the number of independent tests. Each test is specified as follows:

The first line contains R, C, and X (1≤R,C≤5⋅10^5, 0≤X≤min(10^5,RC)), meaning that the grid has dimensions R×C and Farmer John remembers the values of X different cells in the grid.

Then following X lines each contain a character v∈\{+,−\} followed by two integers r and c (1≤r≤R, 1≤c≤C), meaning that the value at the r th row and c th column of the grid is v. It is guaranteed that no ordered pair (r,c) appears more than once within a single test.

Additionally, it is guaranteed that neither the sum of R nor the sum of C over all tests exceeds 10^6, and that the sum of X over all tests does not exceed 2⋅10^5.

Output

For each test, output the number of grids on a separate line.

Subtask

#	Score	Condition
#1	10	min(R,C)=1 for all tests
#2	10	R,C≤10 for all tests
#3	20	∑max(R,C)^2≤10^6
#4	20	∑RC≤10^6
#5	40	No additional constraints.

Example #1

2keyboard_return
1space_bar 3space_bar 3keyboard_return
+space_bar 1space_bar 3keyboard_return
+space_bar 1space_bar 1keyboard_return
-space_bar 1space_bar 2keyboard_return
1space_bar 3space_bar 3keyboard_return
+space_bar 1space_bar 1keyboard_return
+space_bar 1space_bar 3keyboard_return
+space_bar 1space_bar 2

1keyboard_return
0

Example #2

1keyboard_return
2space_bar 2space_bar 0

Here are the seven grids:

Source

USACO 2026 First Contest, Platinum

#8863 upload - done - how_to_reg - call_split Subtask

Pluses and Minuses timer 1s memory 1024MB

Problems translate English text_fields