#8968. 「洛谷 P12062」[THUPC 2025 决赛] 列队 暂未评定

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

定义 为 矩阵 经过如下操作后得到的结果：

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

现给定一个 行 列的整数矩阵 ，满足 且矩阵中元素互不相同。

接下来有 次操作，操作有以下两种：

• 修改操作：给定矩阵中的两个位置 和 ，将这两个位置上的元素交换，即交换 和 。
• 查询操作：给定矩阵中的一个位置 ，输出矩阵 中该位置的元素，即。注意，查询操作并不会真的改变矩阵形态。

第一行依次输入三个整数 。

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

接下来 行，每行先是一个整数 ，表示操作种类。

• 代表一个修改操作。接下来读入四个整数 ，表示交换 和 。

• 代表一个查询操作。接下来读入两个整数 ，表示查询 的值。

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

样例输入 1

复制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

样例输出 1

复制4
3
3
4
1
2

样例 #1 解释

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

1 4
2 3

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

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

4 1
2 3

我们先按行排序，变成

1 4
2 3

再按列排序，变成

1 3
2 4

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

来源与致谢

来自 THUPC2025（2025 年清华大学学生程序设计竞赛暨高校邀请赛）决赛。感谢 THUSAA 的提供的题目。

数据、题面、标程、题解等请参阅 THUPC 官方仓库 https://thusaac.com/public。