King of Data Structures

Heuijiro saw thick grass growing across the lawn near his house one day, so he decided to test the performance of a new lawn mower robot. The lawn is a two-dimensional grid with $n$ rows and $m$ columns. The cell in row $r$ and column $c$ is written $(r,c)$. At the start, every cell of the lawn has grass.

When you enter four integers $d_y$, $d_x$, $y$, $x$ into the robot, it starts at $(y,x)$ and is set to move in the direction $\langle d_y,d_x \rangle$. It is always true that $|d_y|+|d_x|=1$. In other words, the robot always moves in one fixed direction and only to an adjacent cell up, down, left, or right. The robot works as follows.

1. If there is no grass at $(y,x)$, stop mowing.
2. Remove the grass at $(y,x)$.
3. If at least one of the conditions $y+d_y<1$, $y+d_y>n$, $x+d_x<1$, or $x+d_x>m$ is true, stop mowing.
4. Change $(y, x)$ to $(y+d_y, x+d_x)$, then return to step 1.

As part of the performance test, Heuijiro must answer $Q$ queries of the following kinds.

• $1 \ d_y \ d_x \ y \ x$: Start a robot set to direction $\langle d_y,d_x \rangle$ at $(y,x)$, then wait until that robot finishes mowing.
• $2 \ y \ x$: After all mowing jobs started before this query have finished, in order, print the state of $(y,x)$. The state is $0$ if there is grass at $(y,x)$, and $1$ if there is no grass.
• $3$: Print the number of cells that still have grass on the lawn.

If you cannot answer every query exactly, you cannot verify that the robot works correctly. Write a program that answers the given $Q$ queries exactly.

The first line contains the number of rows $n$, the number of columns $m$, and the number of queries $Q$, separated by spaces. ($1 \le n,m \le 1000$, $1 \le Q \le 2\times 10^5$)

From the second line onward, each of the $Q$ lines contains one query. Every query is one of the kinds described in the statement.

For every query, $1 \le y \le n$ and $1 \le x \le m$. For every query of type $1$, $|d_y|+|d_x|=1$.

For every query of type $2$ and type $3$, print the answer on its own line.