Background

Translated from ROI 2019 D1T2.

Today, the capabilities of the newest experimental self-driving taxi need to be demonstrated on the main square of Innopolis. The square is a rectangular area with length $n$ meters and width $m$ meters, divided into $n\times m$ unit cells. The rows of the rectangle are numbered from $1$ to $n$, and the columns are numbered from $1$ to $m$. Therefore, each cell can be represented by two positive integers $r$ and $c$, which are the row and column indices. The self-driving taxi can move between adjacent cells; in one step, it can move from the current cell to one of the four neighboring cells.

This winter there has been a lot of snow, so during the demonstration, automatic snowplows will be used to clear the snow on the square. Since the autonomous traffic system is in the testing stage, at any time there can be only one autonomous vehicle on the square (either a snowplow or the self-driving taxi).

Because it keeps snowing throughout the whole demonstration, the self-driving taxi engineers decided to take the chance to show the taxi’s ability to handle snowdrifts.

Problem Description

At any moment, the snow depth in each unit cell of the square can be represented by a non-negative integer, and the maximum snow depth the self-driving taxi can pass is also a non-negative integer. While moving, the taxi may only stay on cells whose snow depth does not exceed the maximum passable snow depth. For each taxi demonstration, the engineers may set the taxi’s maximum passable snow depth.

Initially, the snow depth in all cells is zero. At the beginning of each hour, the snow depth in every cell increases by one. After that, the autonomous traffic system can perform exactly one of the following three operations, and each operation takes one hour:

1. Start a snowplow along some row, and then the snow depth of all cells in that row becomes zero.
2. Start a snowplow along some column, and then the snow depth of all cells in that column becomes zero.
3. Demonstrate the self-driving taxi: set the taxi’s maximum passable snow depth, choose a start cell and a target cell, and let the taxi travel from the start cell to the target cell.
   The taxi can travel from the start cell to the target cell only if there exists a sequence of unit cells that starts with the start cell and ends with the target cell, where every two consecutive cells share a common side, and every cell in the sequence has snow depth not exceeding the taxi’s maximum passable snow depth. If the chosen maximum passable snow depth makes the trip possible, the taxi should choose a path with the minimum number of steps.

For each taxi demonstration, you need to determine whether the demonstration can be completed successfully (i.e., whether there is a path from the start cell to the target cell). If it is possible, you also need to know the minimum number of steps required to complete the trip.

Input Format

The first line contains three integers $n,m,q$, representing the size of the area and the number of operations on the self-driving taxi system.

The next $q$ lines each describe one operation. In the $i$-th line, the operation is one of the following three types:

• 1 ri: start a snowplow in row $r_i$.
• 2 ci: start a snowplow in column $c_i$.
• 3 ri1 ci1 ri2 ci2 ki: set the taxi’s maximum passable snow depth to $k_i$, and try to drive from the start cell $(r_{i1}, c_{i1})$ to the end cell $(r_{i2}, c_{i2})$.

It is guaranteed that there is at least one operation of type $3$ in the input.

Output Format

For each operation of type $3$, output one integer per line. If the trip from the start cell to the end cell is feasible, output the minimum number of steps needed to complete the trip. If the trip is not feasible, output -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

3
-1
5
-1
3

Hint

Sample Explanation:

The figure shows the snow depth on the square before each operation, and the taxi’s best route for each successful attempt to travel from one cell to another.

Constraints:

Translated by ChatGPT 5