Background

After losing a night of mahjong, Xiao Z and Xiao C uninstalled all card games from their phones. However, this couldn't deter their determination to slack off during class. Now, they've turned their attention to board games, but apart from daily flight chess, they only have a vague understanding of most other games.

"Since we can play but only a little, why not create a hybrid game ourselves?"

Thus, through their creative brainstorming, a unique game blending Go, Chinese Chess, and Military Chess was born...

Problem Description

The game is played on a grid-shaped chessboard with $n$ rows and $m$ columns, where pieces are placed at the intersections of the grid lines. We denote the top-left intersection as $(1,1)$ and the bottom-right as $(n,m)$.

Pieces are divided into black and white, with each player controlling one color.

Each piece has a color and a level. Let $\mathit{col}_i$ be the color of piece $i$ and $\mathit{lv}_i$ be its level. Additionally, the grid lines on the board have 4 states. For the $i$-th grid line, let its state be $\mathit{opt}_i$.

When it's a player's turn, they can choose one of their pieces and move it along the grid lines to another intersection, known as a move. The formal definition of a move is as follows: Select a sequence of coordinates $(x_0,y_0),(x_1,y_1),\ldots,(x_k,y_k)$, where $k$ is a positive integer, $(x_0,y_0)$ is the initial position of the piece, and $(x_k,y_k)$ is the final position. The following conditions must be met:

• For any $i=0,1,\ldots,k-1$, the coordinates $(x_i,y_i)$ and $(x_{i+1},y_{i+1})$ must be directly connected by a grid line, meaning the move must follow the grid lines;
• For any $i\neq j$, it must be that $(x_i,y_i)\neq(x_j,y_j)$, meaning the move cannot pass through the same position, especially $(x_0,y_0)\neq(x_k,y_k)$, meaning the piece cannot stay in place or return to its original position;
• For any $i=1,\ldots,k-1$, the coordinate $(x_i,y_i)$ must be empty, meaning the piece cannot jump over other pieces;
• If $(x_k,y_k)$ is empty, it's a regular move; otherwise, it's a capture. During a capture, let the moving piece's color be $\mathit{col}_1$, level be $\mathit{lv}_1$, the captured piece's color be $\mathit{col}_2$, level be $\mathit{lv}_2$. It must satisfy $\mathit{col}_1\neq\mathit{col}_2,\mathit{lv}_1\geq\mathit{lv}_2$, meaning only pieces of different colors and equal or lower levels can be captured.

Note that, according to the above definition, a piece cannot continue moving after a capture.

The states of the grid lines are as follows:

• If $\mathit{opt}_i=0$, it means the path is blocked, and the piece cannot pass through this grid line;
• If $\mathit{opt}_i=1$, it means this grid line is a "regular road," and a piece can pass through at most one regular road at a time;
• If $\mathit{opt}_i=2$, it means this grid line is a "straight road," and a piece can pass through any number of straight roads but must move straight along either the horizontal or vertical direction without turning. For example, moving from $(1,1)$ through $(1,2)$ to $(1,3)$ is allowed, but from $(1,1)$ through $(1,2)$ to $(2,2)$ is not;
• If $\mathit{opt}_i=3$, it means this grid line is a "connected road," and a piece can pass through any number of connected roads and can turn at any point.

Additionally, during a move, the states of the grid lines traversed must be the same. For example, moving from $(1,1)$ through a straight road to $(1,2)$ and then through a connected road to $(1,3)$ is not allowed.

Other details such as determining the winner are irrelevant to this problem and are omitted.

After developing this chess game, Xiao Z and Xiao C devised a training strategy to improve their skills: Initially, the board is empty, and Xiao C will place a piece on an empty intersection each turn. Xiao Z needs to quickly calculate how many positions on the board can be reached by moving this newly placed piece. Note: This is just a mental exercise, and they won't actually move the piece.

Poor Xiao Z finds his computational skills insufficient for this task and seeks your help.

Input Format

Each test case consists of multiple datasets.

First line: A positive integer $T$ indicating the number of datasets.

For each dataset:

First line: Three positive integers $n, m, q$, representing the number of rows, columns of the board, and the number of rounds, respectively.

Next $n$ lines: Each line is a string of length $m - 1$, with each character being one of $\texttt{0}$, $\texttt{1}$, $\texttt{2}$, $\texttt{3}$, representing the state of the grid line connecting intersection $(i, j)$ to intersection $(i, j + 1)$.

Next $n - 1$ lines: Each line is a string of length $m$, with each character being one of $\texttt{0}$, $\texttt{1}$, $\texttt{2}$, $\texttt{3}$, representing the state of the grid line connecting intersection $(i, j)$ to intersection $(i + 1, j)$.

Next $q$ lines: Each line contains 4 non-negative integers $\mathit{col}_i, \mathit{lv}_i, x_i, y_i$, indicating that in the $i$-th round, a piece of color $\mathit{col}_i$ and level $\mathit{lv}_i$ is placed at intersection $(x_i, y_i)$. Here, $\mathit{col}_i = 0$ denotes a black piece, and $\mathit{col}_i = 1$ denotes a white piece. It is guaranteed that intersection $(x_i, y_i)$ was previously empty.

Output Format

For each dataset, output $q$ lines, each containing a non-negative integer representing the number of intersections that can be reached by the $i$-th piece after it is placed.

Sample Input and Output

Input Sample #1

1
3 3 5
13
22
23
010
233
0 1 2 3
1 2 2 1
1 3 1 2
0 2 3 2
1 3 2 2

Output Sample #1

4
3
3
3
2

Input Sample #2

2
2 3 4
22
33
123
0 2 1 2
0 1 2 1
1 2 1 3
0 3 2 2
3 2 3
3
1
3
32
32
0 2 1 2
1 2 3 2
0 1 2 2

Output Sample #2

3
4
4
2
5
5
1

Input Sample #3

See attached file chess/chess3.in

Output Sample #3

See attached file chess/chess3.ans

Input Sample #4

See attached file chess/chess4.in

Output Sample #4

See attached file chess/chess4.ans

Notes/Hints

[Sample Explanation #1]

After placing piece 1, it can reach positions $(2, 1), (2, 2), (3, 2), (3, 3)$.

After placing piece 2, it can reach positions $(2, 2), (2, 3), (3, 1)$.

After placing piece 3, it can reach positions $(1, 1), (1, 3), (2, 2)$.

After placing piece 4, it can reach positions $(2, 2), (3, 1), (3, 3)$.

After placing piece 5, it can reach positions $(2, 3), (3, 2)$.

[Data Range]

For $100\%$ of the data, $1 \le T \le 5$, $2 \le n, m \le {10}^5$, $4 \le n \times m \le 2 \times {10}^5$, $1 \le q \le \min \{ {10}^5, n \times m \}$, $1 \le \mathit{lv}_i \le q$, $1 \le x_i \le n$, $1 \le y_i \le m$, $\mathit{col}_i \in \{ 0, 1 \}$.

Note: Due to the large input/output size of this problem, it is recommended to use a fast input/output method.

见题面 Input 部分

见题面 Output 部分