题目描述

给你一个图，每个点有点权，最开始没有边。

有一些操作：

1. 添加一条 $x$ 与 $y$ 之间的双向边。

2. 回到第 $x$ 次操作后的状态。（注意这里的 $x$ 可以是 $0$，即回到初始状态）

3. 查询 $x$ 所在联通块能到的点中点权第 $y$ 小的值，如果不存在，那么输出 $-1$。

输入格式

第一行输入两个数 $n,m$，表示有 $n$ 个点，$m$ 个操作。
之后一行 $n$ 个数，表示每个点的点权。
之后 $m$ 行，每行有三种可能的操作：

• 1 x y
• 2 x
• 3 x y

意义见题面。

输出格式

对于所有的 3 操作，输出一个数表示答案。

样例

input

6 10
816801151 223885531 110182151 94271893 319888699 106363731
1 1 3
1 3 5
1 2 4
1 4 6
1 1 2
3 1 1
2 4
1 1 2
3 1 4
2 7

output

94271893
223885531

数据范围与提示

$1 \le n,m \le 100000$

点权在 int 范围内。