Chessboard Movement Reachability

This problem considers a game played on an \(n\)-row by \(m\)-column grid of intersections. The intersections are labeled with coordinates \((1,1)\) at the top‐left and \((n,m)\) at the bottom‐right. Pieces are placed on intersections. Each piece has a color (black or white) and a level. In addition, each grid line (edge) on the board has a type given by an integer \(\mathit{opt}\) which can be 0, 1, 2, or 3. The meaning of an edge with state \(\mathit{opt}\) is as follows:

• \(\mathit{opt}=0\): This road is blocked and cannot be used.
• \(\mathit{opt}=1\): A "normal road" in which a move can traverse at most one such edge.
• \(\mathit{opt}=2\): A "straight road" in which a move can go through an arbitrary number of consecutive roads of type 2; however, the move must continue in the same direction (either horizontal or vertical), no turns allowed.
• \(\mathit{opt}=3\): An "interconnected road" in which a move can traverse arbitrarily many such roads and may turn arbitrarily.

Moves are made as follows. When it is a player’s turn, they choose one of their own pieces and move it along a sequence of intersections \((x_0, y_0), (x_1, y_1), \ldots, (x_k, y_k)\) (with \(k \ge 1\)) such that:

• For every \(i=0,1,\ldots,k-1\), the intersections \((x_i,y_i)\) and \((x_{i+1},y_{i+1})\) are directly connected by a grid line, and the road type of every edge used in the move is the same.
• No intersection is visited twice during the move (in particular, \((x_0,y_0) \neq (x_k,y_k)\)) so that staying in place or returning to the starting position is not allowed.
• For every \(i=1, \ldots, k-1\), the intermediate intersection \((x_i, y_i)\) must be empty (i.e. no piece occupies that intersection).
• If the destination \((x_k,y_k)\) is empty, the move is a normal move; if it is occupied, the move is a capture. In a capture, let the moving piece have color \(\mathit{col}_1\) and level \(\mathit{lv}_1\), and let the captured piece have color \(\mathit{col}_2\) and level \(\mathit{lv}_2\). Then it must hold that \(\mathit{col}_1 \neq \mathit{col}_2\) and \(\mathit{lv}_1 \ge \mathit{lv}_2\). Also, once a capture occurs, the move stops immediately.

The special movement rules for each road type are:

• Type 1 (Normal road): The piece may only move one step along a road of type 1.
• Type 2 (Straight road): The piece may move in one fixed direction (up, down, left, or right) along consecutive type 2 roads until it is blocked or it reaches the board boundary. If the first encountered cell in that direction is occupied, it can be captured only if it is an opponent’s piece and its level is not higher than the moving piece.
• Type 3 (Interconnected road): The piece may move arbitrarily through intersections connected by type 3 roads. In the process, all intermediate intersections must be empty. If an encountered intersection is occupied by an opponent’s piece (with a level not greater than the moving piece), it can be reached by a capture, but the move cannot continue past that intersection.

Initially the board is empty. Then, in a sequence of q moves, a new piece is placed on an empty intersection. After each placement, you are to compute the number of distinct intersections to which that newly placed piece can move (according to the rules above) if it were chosen to move. Note that the piece is not actually moved; only the reachable positions are counted.

inputFormat

The input begins with a line containing three integers \(n, m, q\) \( (2 \le n, m \le 1000,\ 1 \le q \le 10^5)\) representing the number of rows, columns, and queries.

The next \(n\) lines each contain \(m-1\) integers. The \(i\)-th of these lines gives the states of the horizontal grid lines in row \(i\): \(H_{i,1}, H_{i,2}, \ldots, H_{i,m-1}\). That is, \(H_{i,j}\) is the state of the road between intersections \((i,j)\) and \((i,j+1)\). Each \(H_{i,j}\) is an integer in \(\{0,1,2,3\}\).

The next \(n-1\) lines each contain \(m\) integers. The \(i\)-th of these lines gives the states of the vertical grid lines in column order for the gap between row \(i\) and row \(i+1\): \(V_{i,1}, V_{i,2}, \ldots, V_{i,m}\). Here \(V_{i,j}\) is the state of the road between intersections \((i,j)\) and \((i+1,j)\), and each is in \(\{0,1,2,3\}\).

The following \(q\) lines each contain four integers \(col, lv, x, y\). Here, col represents the color of the new piece (for example, 0 for black and 1 for white), lv represents its level, and \(x, y\) (\(1 \le x \le n,\ 1 \le y \le m\)) are the coordinates where the piece is placed. It is guaranteed that the chosen intersection is empty when the piece is placed.

outputFormat

For each query, output a single integer on its own line representing the number of intersections reachable by a move starting from the newly placed piece.

sample

4 4 3
1 3 1
2 2 2
3 3 0
1 1 1
2 3 1 1
3 2 2 1
1 0 3 3
0 5 2 2
1 3 2 3
1 6 3 2

6
3
5