Rock loves drawing. Today, he is trying a new drawing technique.

Rock's canvas can be viewed as a $N \times M$ grid, similar to a Cartesian plane. The bottom left cell is labelled $(1, 1)$ and the top right cell is labelled $(N, M)$. Rock will perform $Q$ queries of the following types:

1. Rock draws a star of color $T_i$ in the cell $(X_i, Y_i)$. Note that Rock may draw multiple stars of any color in the same cell.
2. Rock chooses some diagonal line. Rock wants to know that for the stars on this diagonal line, which color is the majority. We call this color the majority of the diagonal. For some diagonal with $K$ stars, we say color $T$ is the majority of the diagonal if there are more than $\frac{K}{2}$ stars of that color on the diagonal.

It is possible that there is no majority on a diagonal. For example, the majority of $[1, 1, 3]$ is $1$ but there is no majority for $[2, 4], [2, 2, 4, 4, 5]$ or $[]$.

There are two types of diagonal lines Rock is interested in. He will specify it using the parameters $B_i$ and $C_i$.
If $B_i = 1$, Rock refers to the diagonal line of the 🡭 direction starting from cell $(1, C_i)$. The diagonal contains cells $(1, C_i), (2, C_i + 1), (3, C_i + 2), \cdots$.
If $B_i = 2$, Rock refers to the diagonal line of the 🡮 direction starting from cell $(1, C_i)$. The diagonal contains cells $(1, C_i), (2, C_i - 1), (3, C_i - 2), \cdots$.

Input

The first line of input contains three integers $N$, $M$ and $Q$.
Each of the following $Q$ lines contains the parameters to a query.
The first integer on the line is the type of the query $A_i$. $(1 \le A_i \le 2)$
If $A_i = 1$, three integers $T_i$, $X_i$ and $Y_i$ follow. $(1 \le T_i \le Q, 1 \le X_i \le N, 1 \le Y_i \le M)$
If $A_i = 2$, two integers $B_i$ and $C_i$ follow. $(1 \le B_i \le 2, 1 \le C_i \le M)$

Output

For each query of type 2, output an integer on a line denoting the majority of the diagonal, or -1 if there is no majority.

Constraints

For all subtasks, $1 \le N,M \le 10^9, 1 \le Q \le 10^5$
Subtask 1 (5%): $N=1$ or $M=1$
Subtask 2 (20%): $N \times M, Q \le 2000$
Subtask 3 (15%): $C_i=1$ for all queries of type 2
Subtask 4 (20%): $Q \le 2000$
Subtask 5 (40%): No additional constraints