在因诺波利斯（Innopolis）的主广场上，计划进行一场无人驾驶出租车的性能演示。广场是一个 $n \times m$ 米的矩形，被划分为若干个单位正方形。矩形的行编号从 $1$ 到 $n$，列编号从 $1$ 到 $m$。因此，每个正方形由两个正整数 $r$ 和 $c$ 唯一确定，分别表示其所在的行号和列号。在广场上移动时，无人驾驶出租车在单位正方形之间穿行，每一步它可以从当前所在的方格移动到与其有公共边的相邻方格。

今年的冬天雪量很大，为了在演示过程中清理广场，计划使用无人驾驶扫雪车。由于无人驾驶交通管理系统处于测试模式，因此广场上同一时间只能有一辆无人驾驶车辆。

由于在整个演示过程中雪一直在下，无人驾驶出租车的工程师们决定展示其克服积雪的能力。在任何时刻，广场上每个单位正方形的积雪深度都由一个非负整数表示。无人驾驶出租车的通行能力也由一个非负整数设定。在广场上移动时，出租车只能停留在积雪深度不超过其通行能力的单位正方形上。在每次行程之前，工程师可以配置出租车，设定其通行能力的值。

初始时，整个广场的积雪深度为零。在每个小时开始时，每个方格的积雪深度增加 $1$。此后，无人驾驶交通管理系统可以执行以下三种操作之一，每种操作恰好耗时一小时：

1) 沿某一行运行扫雪车，之后该行所有方格的积雪深度变为零； 2) 沿某一列运行扫雪车，之后该列所有方格的积雪深度变为零； 3) 展示无人驾驶出租车的能力：设定其通行能力值，选择起始和终止单位正方形，并尝试驾驶出租车从起始方格行驶到终止方格。

如果存在一个单位正方形序列，从起始单位正方形开始，到终止单位正方形结束，其中任意两个相邻方格都有公共边，且序列中每个方格的积雪深度都不超过出租车的通行能力，则从起始方格到终止方格的行程是可能的。如果设定的通行能力允许完成行程，出租车必须使用步数最少的路径。

对于无人驾驶出租车的每次行程，需要确定是否可以完成行程，如果可以，完成该行程所需的最少步数是多少。

输入格式

输入的第一行包含三个整数 $n$、$m$ 和 $q$ —— 广场的尺寸和无人驾驶出租车管理系统执行的操作数量 ($1 \leqslant n, m \leqslant 10^6$, $1 \leqslant q \leqslant 300\,000$)。

接下来的 $q$ 行包含操作描述，第 $i$ 行包含以下三种类型之一：

• “$1\ r_i$” —— 沿行 $r_i$ 运行扫雪车 ($1 \leqslant r_i \leqslant n$)。
• “$2\ c_i$” —— 沿列 $c_i$ 运行扫雪车 ($1 \leqslant c_i \leqslant 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 \leqslant r_{i,1}, r_{i,2} \leqslant n$, $1 \leqslant c_{i,1}, c_{i,2} \leqslant m$, $0 \leqslant k_i \leqslant q$，方格 $(r_{i,1}, c_{i,1})$ 和 $(r_{i,2}, c_{i,2})$ 不同)。

保证输入数据中至少包含一个类型 3 的操作。

输出格式

对于每个类型 3 的操作，需要输出一行。如果从起始方格到终止方格的行程是可能的，则输出完成行程所需的最少步数。如果行程不可能，则输出 $-1$。

评分系统

样例

输入格式 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

输出格式 1

3
-1
5
-1
3

说明

图示展示了示例中每次操作前广场上的积雪深度，以及每次成功尝试从一个方格行驶到另一个方格时的出租车最优路径。

在示例中，广场大小为 $4 \times 3$。 - 在第一次操作（类型 3）中，通行能力为 1。起始方格 $(2, 1)$ 和终止方格 $(3, 3)$ 的积雪深度均为 0。路径为 $(2, 1) \to (2, 2) \to (2, 3) \to (3, 3)$，长度为 3。 - 在第二次操作（类型 3）中，通行能力为 1。由于此时积雪深度增加，无法到达。 - 在第五次操作（类型 3）中，通行能力为 3。路径为 $(2, 1) \to (1, 1) \to (1, 2) \to (1, 3) \to (2, 3) \to (3, 3)$，长度为 5。