题目背景

English statement. You must submit your code at the Chinese version of the statement.

秋雨刚刚亲吻过大地，白云便卷起赤橙黄绿青蓝紫。

波长在可见光范围内自由落体，让蒸腾的水汽都带上了递进的旋律。

渐变色模糊的印象总被晴天匆匆带过，但往往反常的极差让我们更加记忆犹新。

所以有序，真的最优吗？

题目描述

小 C 有 $m$ 个整数序列 $a_1\dots a_m$，每个序列的长度都为 $n$。

小 C 想要把自己的序列按照整数大小排序。于是小 C 有 $q$ 次操作，每次操作：

• 要么，小 C 给出 $x, y\ (x \neq y)$，他想把 $a_x, a_y$ 拼接在一起形成长度为 $2n$ 的序列 $b$，将 $b$ 升序排序后取 $b_1\dots b_n$ 作为新的 $a_x$，$b_{n+1}\dots b_{2n}$ 作为新的 $a_y$；
• 要么，小 C 给出 $i, j$，细心的小 C 想要询问你，经过前面的若干次操作后，$a_{i,j}$ 的值，你需要准确回答他的问题。

输入格式

第一行，三个整数 $n, m, q$。

接下来 $m$ 行，每行 $n$ 个整数，第 $i$ 行 $j$ 个整数表示 $a_{i,j}$。

接下来 $q$ 行，每行三个整数，描述一次操作或询问。其格式为下述两种之一：

• $\verb!1 x y!$ 表示对 $a_x, a_y$ 进行排序，其中 $1 \leq x \neq y \leq m$；
• $\verb!2 i j!$ 表示查询 $a_{i,j}$，其中 $1 \leq i \leq m$，$1 \leq j \leq n$。

输出格式

对于每组询问，一行一个整数，表示答案。

5 3 6
1 3 2 5 6
2 7 8 2 2
3 5 3 4 8
2 1 5
1 1 2
2 2 4
1 1 3
1 2 1
2 2 3

6
7
2

6 5 20
5 14 13 1 15 17
7 7 19 3 8 6
16 13 13 6 14 2
12 5 4 17 12 3
19 19 4 6 3 3
2 5 3
1 4 3
2 1 1
1 2 5
2 4 6
2 2 2
1 4 2
1 2 4
2 1 1
2 3 3
2 3 3
1 4 2
1 4 1
2 3 5
1 3 4
1 4 1
1 1 4
1 5 1
2 2 4
2 4 2

4
5
12
3
5
13
13
16
6
14

提示

数据规模与约定

本题采用捆绑测试和子任务依赖。

因为最后两个 Subtask 的极限输入数据大小分别达到 18MB、50MB 以上，C++ 选手可以选择使用下面的 快速输入输出模板：

namespace FastIO {
	char buf[1 << 21], *p1 = buf, *p2 = buf;
#define getchar() (p1 == p2 && (p1 = buf, p2 = (p1 + fread(buf, 1, 1 << 21, stdin))) == p1 ? EOF : *p1++)
	template <typename T> inline T read() { T x = 0, w = 0; char ch = getchar(); while (ch < '0' || ch > '9') w |= (ch == '-'), ch = getchar(); while ('0' <= ch && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar(); return w ? -x : x; }
	template <typename T> inline void write(T x) { if (!x) return; write<T>(x / 10), putchar((x % 10) ^ '0'); }
	template <typename T> inline void print(T x) { if (x > 0) write<T>(x); else if (x < 0) putchar('-'), write<T>(-x); else putchar('0'); }
	template <typename T> inline void print(T x, char en) { print<T>(x), putchar(en); }
}; using namespace FastIO;
#undef getchar()

不保证除了 C++ 以外的语言一定能够通过，但保证对于 C++ 语言有充足的时限。

---

• Subtask 0（0 pts）：样例。
• Subtask 1（9 pts）：$n \leq 10^4$，$q \leq 3000$。依赖于子任务 $0$。
• Subtask 2（23 pts）：$q \leq 3000$。依赖于子任务 $0, 1$。
• Subtask 3（20 pts）：$m \leq 5$，$q \leq 4\times 10^5$。依赖于子任务 $0$。
• Subtask 4（28 pts）：$q \leq 4\times 10^5$。依赖于子任务 $0 \sim 3$。
• Subtask 5（20 pts）：无特殊限制。依赖于子任务 $0 \sim 4$。

对于所有数据，满足 $1 \leq n\cdot m \leq 2\times 10^6$，$1 \leq m \leq 20$，$1 \leq q \leq 5\times 10^6$，$1 \leq a_{i,j} \leq 10^7$；对于操作或询问，$1 \leq x \neq y \leq m$，$1 \leq i \leq m$，$1 \leq j \leq n$。