19907번 - Беспилотное такси 서브태스크다국어

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

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

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

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

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

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

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

Первая строка ввода содержит три целых числа $n$, $m$ и $q$ --- размеры площади и количество действий, которые совершаются системой управления беспилотными такси ($1 \le n, m \le 10^6$, $1 \le q \le 300\,000$).

Следующие $q$ строк содержат описания действий, $i$-я из них имеет один из следующих трех типов:

• <<$1~r_i$>> --- запустить снегоуборочную машину вдоль строки $r_i$ ($1 \le r_i \le n$).
• <<$2~c_i$>> --- запустить снегоуборочную машину вдоль столбца $c_i$ ($1 \le c_i \le m$).
• <<$3~r_{i, 1}~c_{i, 1}~r_{i, 2}~c_{i, 2}~k_i$>> --- задать для такси значение проходимости, равное $k_i$, и попытаться проехать от единичного квадрата $(r_{i, 1}, c_{i,1})$ до единичного квадрата $(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$, квадраты $(r_{i, 1}, c_{i,1})$ и $(r_{i,2}, c_{i,2})$ различны).

Гарантируется, что во входных данных есть хотя бы одно действие типа 3.

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

На рисунке приведены уровни снега на площади перед каждым действием в примере и оптимальный маршрут такси для каждой успешной попытки проехать от одного квадрата до другого.