题目描述

给定一个有 $n$ 个顶点的图。接下来有 $q$ 次询问，询问共有三种类型：

1. 在顶点 $v_i$ 所在的连通块中，找到编号第 $k_i$ 小的顶点编号。如果不存在这样的顶点，则返回 $-1$。顶点 $v_i$ 所在的连通块，指所有可以从 $v_i$ 沿图中的边到达的顶点组成的集合。
2. 向图中加入一条连接顶点 $u_i$ 和 $v_i$ 的边。
3. 回到执行完 $x_i$ 次操作之后的图的状态。

请输出所有第一类询问的答案。

输入格式

第一行包含三个整数 $n,q,g$，其中 $1 \le n,q \le 5 \times 10^5$，$0 \le g \le 9$。

接下来 $q$ 行，每行描述一次询问。询问格式如下：

• 第一类询问：1 v_i k_i，其中 $1 \le v_i,k_i \le n$；
• 第二类询问：2 v_i u_i，其中 $1 \le v_i,u_i \le n$；
• 第三类询问：3 x_i，其中 $0 \le x_i < i$。

这里第 $i$ 次操作中的 $x_i$ 表示回到“已经执行完 $x_i$ 次操作之后”的状态。特别地，$x_i=0$ 表示回到初始状态。

输出格式

对于每个第一类询问，输出一行一个整数，表示该询问的答案。

样例 1

输入

10 12 0
1 1 1
2 1 2
2 1 6
2 9 10
2 3 10
2 10 6
1 1 5
1 1 3
3 5
1 1 3
3 0
1 1 3

输出

1
9
3
6
-1

样例 2

输入

10 17 0
2 1 2
1 2 2
2 3 4
1 3 2
2 6 7
2 7 8
1 7 2
1 7 3
2 5 6
1 5 5
1 5 4
2 5 4
2 3 2
1 1 7
1 1 4
1 1 8
1 1 9

输出

2
4
7
8
-1
8
7
4
8
-1

样例 3

输入

6 14 0
2 1 6
2 1 3
1 3 2
1 3 3
1 1 1
1 2 1
1 2 6
2 1 2
2 2 2
2 2 1
2 1 5
2 1 4
1 6 6
1 1 5

输出

3
6
1
2
-1
6
5

样例 4

输入

5 5 0
2 1 2
1 1 2
3 0
2 1 3
1 1 2

输出

2
3

评分方式

1. $6$ 分：$n,q \le 100$，没有第二类和第三类操作。
2. $7$ 分：$n,q \le 100$，没有第三类操作。
3. $4$ 分：$n,q \le 100$。
4. $9$ 分：$n,q \le 3 \times 10^5$，保证所有第二类操作中 $|v_i-u_i|=1$，且没有第三类询问。
5. $8$ 分：$n,q \le 3 \times 10^5$，没有第三类询问。
6. $10$ 分：$n,q \le 3 \times 10^5$，保证所有第二类操作中 $|v_i-u_i|=1$。
7. $19$ 分：$n,q \le 10^5$。
8. $17$ 分：$n,q \le 3 \times 10^5$。
9. $20$ 分：无额外限制。