Background

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

After the autumn rain has just kissed the earth, white clouds roll up red, orange, yellow, green, cyan, blue, and purple.

Wavelengths within the visible light range fall freely, giving the rising water vapor a gradually changing rhythm.

The blurry impression of gradients is always hurried past by sunny days, but the often unusual range makes us remember it more clearly.

So, is being ordered really optimal?

Problem Description

Xiao C has $m$ integer sequences $a_1 \dots a_m$, and each sequence has length $n$.

Xiao C wants to sort his sequences by integer value. So Xiao C has $q$ operations. In each operation:

• Either, Xiao C gives $x, y\ (x \neq y)$. He wants to concatenate $a_x$ and $a_y$ into a sequence $b$ of length $2n$. After sorting $b$ in nondecreasing order, take $b_1 \dots b_n$ as the new $a_x$, and take $b_{n+1} \dots b_{2n}$ as the new $a_y$.
• Or, Xiao C gives $i, j$. Careful Xiao C wants to ask you: after the previous operations, what is the value of $a_{i,j}$? You need to answer his question exactly.

Input Format

The first line contains three integers $n, m, q$.

The next $m$ lines each contain $n$ integers. The $j$-th integer on the $i$-th line denotes $a_{i,j}$.

The next $q$ lines each contain three integers, describing one operation or one query, in one of the following two formats:

• $\verb!1 x y!$ means sorting $a_x$ and $a_y$, where $1 \leq x \neq y \leq m$.
• $\verb!2 i j!$ means querying $a_{i,j}$, where $1 \leq i \leq m$ and $1 \leq j \leq n$.

Output Format

For each query, output one integer per line, representing the answer.

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

Hint

Constraints

This problem uses bundled test and subtask dependencies.

Because the maximum input sizes of the last two subtasks reach $18\text{MB}$ and more than $50\text{MB}$ respectively, C++ users may choose to use the following fast I/O template:

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()

It is not guaranteed that languages other than C++ can pass, but sufficient time limits are guaranteed for C++.

• Subtask 0 (0 pts): samples.
• Subtask 1 (9 pts): $n \leq 10^4$, $q \leq 3000$. Depends on Subtask $0$.
• Subtask 2 (23 pts): $q \leq 3000$. Depends on Subtasks $0, 1$.
• Subtask 3 (20 pts): $m \leq 5$, $q \leq 4\times 10^5$. Depends on Subtask $0$.
• Subtask 4 (28 pts): $q \leq 4\times 10^5$. Depends on Subtasks $0 \sim 3$.
• Subtask 5 (20 pts): no special constraints. Depends on Subtasks $0 \sim 4$.

For all testdata, $1 \leq n \cdot m \leq 2\times 10^6$, $1 \leq m \leq 20$, $1 \leq q \leq 5\times 10^6$, and $1 \leq a_{i,j} \leq 10^7$. For each operation or query, $1 \leq x \neq y \leq m$, $1 \leq i \leq m$, and $1 \leq j \leq n$.

Translated by ChatGPT 5