The main square of Innopolis is planned to host a demonstration of autonomous taxi capabilities. The square is a rectangle of size $n \times m$ meters, divided into unit squares. The rows of the rectangle are numbered from $1$ to $n$, and the columns from $1$ to $m$. Thus, each square is characterized by two positive integers $r$ and $c$ — the row and column numbers of its location. When moving across the square, an autonomous taxi moves between unit squares; in one step, it can move from its current square to a square that shares a side with it.

This winter has been snowy, and autonomous snowplows are planned to be used to clear the square during the demonstration. The autonomous transport control system is in testing mode, so only one autonomous vehicle can be on the square at any given time.

Since snow continues to fall throughout the demonstration, the engineers of the autonomous taxi decided to demonstrate its ability to overcome snowdrifts. At any moment, the snow depth on each unit square of the square is characterized by a non-negative integer. The taxi's passability is also defined by a certain non-negative integer. When moving across the square, the taxi can only be on those unit squares where the snow depth does not exceed its passability. Before each trip, the engineers can configure the taxi by setting its passability value.

Initially, the snow depth on the entire square is zero. At the beginning of each hour, the snow depth on each square increases by one. After that, the autonomous transport control system can perform one of three actions, each of which takes exactly one hour:

1) Run a snowplow along a row, after which the snow depth on all squares of this row becomes zero; 2) Run a snowplow along a column, after which the snow depth on all squares of this column becomes zero; 3) Demonstrate the autonomous taxi's capabilities: set its passability value, choose starting and finishing unit squares, and attempt to drive the taxi from the starting square to the finishing one.

A trip from the starting square to the finishing square is possible if there exists a sequence of unit squares starting at the starting square and ending at the finishing one, in which any two adjacent squares share a side, and the snow depth on each square in the sequence does not exceed the taxi's passability. If the set passability value allows the trip to be completed, the taxi must use a path with the minimum number of steps.

For each autonomous taxi trip, it is required to determine whether it is possible to complete the trip, and if so, what the minimum number of steps required to complete this trip is.

Input

The first line of input contains three integers $n$, $m$, and $q$ — the dimensions of the square and the number of actions performed by the autonomous taxi control system ($1 \le n, m \le 10^6$, $1 \le q \le 300\,000$).

The following $q$ lines contain descriptions of the actions, the $i$-th of which is of one of the following three types:

• "1 $r_i$" — run a snowplow along row $r_i$ ($1 \le r_i \le n$).
• "2 $c_i$" — run a snowplow along column $c_i$ ($1 \le c_i \le m$).
• "3 $r_{i,1}$ $c_{i,1}$ $r_{i,2}$ $c_{i,2}$ $k_i$" — set the taxi's passability to $k_i$ and attempt to drive from unit square $(r_{i,1}, c_{i,1})$ to unit square $(r_{i,2}, c_{i,2})$ ($1 \le r_{i,1}, r_{i,2} \le n$, $1 \le c_{i,1}, c_{i,2} \le m$, $0 \le k_i \le q$, the squares $(r_{i,1}, c_{i,1})$ and $(r_{i,2}, c_{i,2})$ are distinct).

It is guaranteed that the input contains at least one action of type 3.

Output

For each action of type 3, output a single line. If the trip from the starting square to the finishing square is possible, output the minimum number of steps required to complete the trip. If the trip is impossible, output $-1$.

Subtasks

Examples

Input 1

4 3 9
3 2 1 3 3 1
3 2 1 3 3 1
2 1
2 3
1 1
3 2 1 3 3 3
3 2 1 3 3 3
2 2
3 2 1 3 3 6

Output 1

3
-1
5
-1
3

Note

The figures show the snow levels on the square before each action in the example and the optimal taxi route for each successful attempt to drive from one square to another.

(2, 1) → (3, 3), k = 1

(2, 1) → (3, 3), k = 1

(2, 1) → (3, 3), k = 3

(2, 1) → (3, 3), k = 3

(2, 1) → (3, 3), k = 3

(2, 1) → (3, 3), k = 6