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

---

题目描述

定义 $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)$，将这两个位置上的元素交换，即交换 $P_{x_1y_1}$ 和 $P_{x_2y_2}$。
• 查询操作：给定矩阵中的一个位置 $(x,y)$，输出矩阵 $f(P)$ 中该位置的元素，即 $f(P)_{xy}$。注意，查询操作并不会真的改变矩阵形态。

---

输入格式

第一行依次输入三个整数 $n,m,q$ $(1\le n\times m\le2\times10^5,\ 1\le q\le2\times10^5)$。

接下来 $n$ 行，每行 $m$ 个整数，依次描述矩阵 $P$ 各行各列的元素。保证这些元素均在 $1\sim n\times m$ 之间且互不相同。

接下来 $q$ 行，每行先是一个整数 $\text{opt}\in\{1,2\}$，表示操作种类。

• $\text{opt}=1$ 代表一个修改操作。接下来读入四个整数 $x_1,y_1,x_2,y_2$ $(1\le x_1,x_2\le n,\ 1\le y_1,y_2\le m)$，表示交换 $P_{x_1y_1}$ 和 $P_{x_2y_2}$。
• $\text{opt}=2$ 代表一个查询操作。接下来读入两个整数 $x,y$ $(1\le x\le n,\ 1\le y\le m)$，表示查询 $f(P)_{xy}$ 的值。

---

输出格式

对每组查询操作，输出对应元素的值。

---

样例

输入

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

• 第一次查询的时候矩阵形如

$$\begin{matrix} 1 & 4 \\ 2 & 3 \end{matrix}$$

我们发现第一次按行排列时就没能使得矩阵改变，因此答案就是第一行第二列的元素，也就是 $4$。

• 第二次查询的时候矩阵形如

$$\begin{matrix} 4 & 1 \\ 2 & 3 \end{matrix}$$

我们先按行排序，变成

$$\begin{matrix} 1 & 4 \\ 2 & 3 \end{matrix}$$

再按列排序，变成

$$\begin{matrix} 1 & 3 \\ 2 & 4 \end{matrix}$$

再尝试按行排序，发现不能成功排序。因此答案就是此时第一行第二列的元素，也就是 $3$。

---

题目使用协议
来自 THUPC2025（2025年清华大学学生程序设计竞赛暨高校邀请赛）。

以下『本仓库』皆指 THUPC2025 官方仓库（https://gitlink.org.cn/thusaa/thupc2025final）

任何单位或个人都可以免费使用或转载本仓库的题目；
任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限；
如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库地址 或 算协公开仓库链接。