题目描述

译自 ROI 2019 Day1 T2. Беспилотное такси

Innopolis 有一片长 $n$ 米宽 $m$ 米的矩形广场，它被划分为 $n$ 行 $m$ 列单位正方形（单元格），行被依次编为第 $1\ldots n$ 行，列被依次编为第 $1\ldots m$ 列。第 $r$ 行第 $c$ 列的单元格可以用 $(r,c)$ 表示。

我们计划在这个广场上展示无人驾驶出租车。开始时，场地里只有一辆车，车在一个单元格内。又到了白色相簿的季节， 展演过程中一直在下雪。每个单元格上的积雪可以用一个自然数表示。最初，整个区域的积雪深度为零。在每个小时的开始，每个方格的积雪深度增加一。车有一个可调整的「最大踏雪深度」，车子只能到达积雪深度不超过最大踏雪深度的单元格上。

车上加装了一个吹雪机。每小时无人驾驶汽车可以完成以下三种操作中的任意一种：

1. 把它所在行的雪吹光，该行所有单元格的雪的深度均变为 0；
2. 把它所在列的雪吹光，该列所有单元格的雪的深度均变为 0；
3. 演示者设定最大踏雪深度，并指定起点和终点，无人驾驶汽车尝试从起点行驶到终点。

无人驾驶汽车每一步可以从一个单元格移到与该单元格有公共边的另一个单元格。如果从起点到终点能找到一条包含若干步的路径，且路径上（含起终点）所有单元格的雪深均不超过最大踏雪深度，则称从起点到终点「可行」。如果从起点到终点可行，无人驾驶汽车会选择步数最少的路径。

对于每个第 3 种操作，你需要确定能否执行行程，若行，请给出最少步数。

На главной площади Иннополиса планируется демонстрация возможностей беспилотных такси. Площадь имеет форму прямоугольника размером n × m метров, разделённого на единичные квадраты. Строки прямоугольника пронумерованы от 1 до n, а столбцы — от 1 до m. Таким образом, каждый квадрат характеризуется двумя положительными числами r и c — номерами строки и столбца, на пересечении которых он находится. При движении по площади беспилотное такси перемещается между единичными квадратами, за один шаг оно может переместиться из квадрата, в котором оно сейчас находится, в квадрат, имеющий с ним общую сторону.

Зима в этом году выдалась снежная, и для уборки площади в процессе демонстрации планируется использовать беспилотные снегоуборочные машины. При этом система управления беспилотным транспортом находится в режиме тестирования, поэтому одновременно на площади может находиться только одно беспилотное транспортное средство.

Поскольку снег продолжает идти в течение всей демонстрации, инженеры беспилотного такси решили продемонстрировать его возможности по преодолению сугробов. В каждый момент времени глубина снега на каждом единичном квадрате площади характеризуется неотрицательным целым числом. Проходимость беспилотного такси также задаётся некоторым неотрицательным целым числом. При перемещении по площади такси может находиться только на тех единичных квадратах, глубина снега на которых не превышает его проходимости. Перед каждой поездкой инженеры могут настроить такси, задав при этом значение его проходимости.

Исходно глубина снега на всей площади равна нулю. В начале каждого часа глубина снега на каждом квадрате увеличивается на один. После этого система управления беспилотным транспортом может выполнить одно из трех действий, каждое из которых занимает ровно один час:

1. запустить снегоуборочную машину вдоль строки, после этого на всех квадратах этой строки глубина снега становится равной нулю;
2. запустить снегоуборочную машину вдоль столбца, после этого на всех квадратах этого столбца глубина снега становится равной нулю;
3. продемонстрировать возможности беспилотного такси: задать значение его проходимости, выбрать стартовый и финишный единичные квадраты, и попытаться проехать на такси от стартового квадрата до финишного.

Поездка от стартового до финишного квадрата возможна, если существует последовательность единичных квадратов, начинающаяся в стартовом единичном квадрате и завершающаяся в финишном, в которой любые два соседних квадрата имеют общую сторону, и глубина снега на каждом из квадратов последовательности не превышает проходимости такси. Если выставленное значение проходимости позволяет осуществить поездку, такси должно использовать путь с минимальным количеством шагов.

Для каждой поездки на беспилотном такси требуется определить, возможно ли осуществить поездку, и если да, то какое минимальное количество шагов потребуется для осуществления этой поездки.

输入格式

$n\,\,m\,\,q$
接下来 $q$ 行，每行一组操作：

• 第 1 种操作：$\large\texttt{1}\,\,r_i$
• 第 2 种操作：$\large\texttt{2}\,\,c_i$
• 第 3 种操作：$\large\texttt{3}\,\,r_{i,1}\,\,c_{i,1}\,\,r_{i,2}\,\,c_{i,2}\,\,k_{i}$

输出格式

对于每个第 3 种操作，输出一行，每行一个整数，如有解，则给出最少步数，如无解则输出 -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

数据范围与提示

对于所有数据，$1 ⩽ n, m ⩽ 10^6$，$1 ⩽ q ⩽ 3×10^5$。