Vacuum Cleaner

Paolo works as a janitor in a large storage hall. Two of his tasks are vacuuming and moving objects around the hall. Paolo is fairly pragmatic about cleaning. He waits until there is so much dust that objects can no longer be moved. To make things worse, he recently bought a robot vacuum cleaner and releases it instead of cleaning himself. The robot is broken and cannot turn. It moves in a straight line until it hits a wall and runs out of battery.

The hall is an $N \times M$ grid. Rows are numbered 1 to $N$, and columns are numbered 1 to $M$. Every cell starts with 0 units of dust. Then $Q$ days follow. Each day begins with the dust in every cell increasing by 1. After that, exactly one of three things happens.

1. An event of the form $1$ $r$ means Paolo releases the robot along row $r$, so the dust in every cell of that row becomes 0.
2. An event of the form $2$ $c$ means Paolo releases the robot along column $c$, so the dust in every cell of that column becomes 0.
3. An event of the form $3$ $r_1$ $c_1$ $r_2$ $c_2$ $k$ means Paolo needs to move something from cell $(r_1, c_1)$ to cell $(r_2, c_2)$. The value $k$ is the item's dust tolerance. The item can only be moved across cells with at most $k$ units of dust. For example, if $(r_1, c_1)$ or $(r_2, c_2)$ has more than $k$ units, the task cannot be completed.

For each event of type 3, output the minimum number of steps Paolo needs to move the item. In one step he moves to a adjacent cell, meaning a cell that shares a side. Cells on the edge have fewer than four neighbors. If the item cannot be moved, output $-1$.

The first line contains three integers $N$, $M$, and $Q$ ($1 \leq N,M \leq 10^6$, $1 \leq Q \leq 3 \cdot 10^5$).

Each of the next $Q$ lines describes an event. Each line starts with an integer $t$, which is 1, 2, or 3, indicating the type of event. If $t = 1$, the same line contains one more integer $r$ ($1 \leq r \leq N$), the row that was chosen. If $t = 2$, the line contains an integer $c$ ($1 \leq c \leq M$), the column that was chosen. If $t = 3$, the line contains five more integers $r_1$, $c_1$, $r_2$, $c_2$, $k$ ($1 \leq r_1, r_2 \leq N$, $1 \leq c_1, c_2 \leq M$, $0 \leq k \leq Q$).

For every event of type 3, the cells $(r_1, c_1)$ and $(r_2, c_2)$ are different. There is at least one event of type 3.

For each event of type 3, print one line with the minimum number of steps needed to move the item. If the item cannot be moved, print $-1$ instead.