Background

……所以这个题意和标题是什么关系？

Description

定义 $f(A)$ 为矩阵 $A$ 经过如下操作后得到的结果：

1. 独立地对矩阵 $A$ 的每行进行排序，使得各行中的元素从左到右单调不降。 如果排序过后的矩阵和排序之前完全相同，则此次变换停止，否则进行步骤 2。
2. 独立地对矩阵 $A$ 的每列进行排序，使得各列中的元素从上到下单调不降。 如果排序过后的矩阵和排序之前完全相同，则此次变换停止，否则继续步骤 1。

现给定一个 $n$ 行 $m$ 列的整数矩阵 $P$，满足 $1\le P_{ij} \le n\times m$ 且矩阵中元素互不相同。

接下来有 $q$ 次操作，操作有两种类型：

• 修改操作：给定矩阵中的两个位置 $(x_1,y_1)$ 和 $(x_2,y_2)$，交换这两个位置上的元素；
• 查询操作：给定矩阵中的一个位置 $(x,y)$，输出矩阵 $f(P)$ 中该位置的元素。 查询操作不会真的改变矩阵形态。

Format

Input

第一行三个整数 $n, m, q$，满足：

$$1 \le n \times m \le 2\times 10^5, \quad 1 \le q \le 2\times 10^5 $$

接下来 $n$ 行，每行 $m$ 个整数，描述矩阵 $P$ 的初始状态，元素范围在 $[1, n\times m]$ 且互不相同。

接下来 $q$ 行，每行描述一个操作：

• 1 x1 y1 x2 y2 表示交换 $P_{x_1,y_1}$ 与 $P_{x_2,y_2}$；
• 2 x y 表示查询 $f(P)_{x,y}$ 的值。

Output

对每个查询操作，输出对应的值。

Samples

2 2 10
1 4
2 3
2 1 2
1 1 1 1 2
2 1 2
1 1 1 1 2
1 1 2 2 1
2 2 1
2 2 2
1 1 1 2 2
2 1 1
2 2 1

4
3
3
4
1
2

样例解释：

第一次查询时矩阵为：

1 4
2 3

按行排序没有变化，因此直接取 $(1,2)$ 元素 = 4。

修改后矩阵为：

4 1
2 3

按行排序：

1 4
2 3

再按列排序：

1 3
2 4

再次按行排序无变化，因此 $(1,2)$ 元素 = 3。