Description

每个时刻广场上每个单位方块的雪深可以由一个非负整数表示，自动驾驶出租车的最大可通过雪深也由一个非负整数表示。在移动时，出租车只能停留在雪深不超过最大可通过雪深的方块上。每次展示自动驾驶出租车时，工程师可以设置出租车的最大可通过雪深。

初始状态下，广场上所有方块的雪深为零。每个小时开始时，每个方块的雪深增加一。随后，自动驾驶交通系统可以执行以下三个操作之一，每个操作需要一小时：

1. 沿着某一行启动除雪机，然后该行的所有方块的雪深变为零；
2. 沿着某一列启动除雪机，然后该列的所有方块的雪深变为零；
3. 展示自动驾驶出租车的功能：设置出租车的最大可通过雪深，选择起始和目标方格，并让出租车从起始方块到达目标方块。
   只有当存在一个以起始方块开始、以目标方块结束的单位方块序列，其中任意相邻的两个方块有共同的边界，并且序列中每个方块的雪深都不超过出租车的最大可通过雪深时，才可以从起始方块到达目标方块。如果设置的最大可通过雪深允许完成旅行，则出租车应选择步数最少的路径。

每次展示自动驾驶出租车时，需要确定是否可以顺利完成这次的展示（是否有从起始方块到目标方块的路径），如果可以，则需要知道完成此次旅行所需的最少步数。

Input Format

第一行包含三个整数 $n,m,q$，分别表示区域的大小和无人驾驶出租车的操作数。

接下来的 $q$ 行，每行输入一种操作，其中第 $i$ 行有以下三种操作类型之一：

• 1 ri：在第 $r_i$ 行启动除雪机。
• 2 ci：在第 $c_i$ 列启动除雪机。
• 3 ri1 ci1 ri2 ci2 ki：设置出租车的最大可通过雪深为 $k_i$，并尝试从起始方格 $(r_{i1}, c_{i1})$ 开始行驶到结束方格 $(r_{i2}, c_{i2})$。

保证输入数据中至少存在一个类型为 $3$ 的操作。

Output Format

对于每个类型为 $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

Hint

样例解释：

图中显示了每次操作前广场上的雪层深度以及每次成功尝试从一个方块到另一个方块的出租车最佳路线。

数据范围：