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

有一些操作：

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$ 的操作，输出一行，包含一个整数，表示答案。

样例数据

样例输入

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

样例输出

94271893
223885531

子任务

Idea：nzhtl1477，

Solution：nzhtl1477( $O( nm/w )$ Time , $O( n\log n )$ Space )，ccz181078( $O( m\sqrt{n\log n} )$ Time ，$O(n\sqrt{n\log n} )$ Space ) ，shadowice1984( $O( m\sqrt{n\log n} )$ Time , $O( n\log n )$ Space ) , zx2003( $O( m\sqrt{n} )$ Time ，$O( n )$ Space )

Code：nzhtl1477( $O( nm/w )$ Time , $O( n\log n )$ Space )，ccz181078( $O( m\sqrt{n\log n} )$ Time , $O( n\sqrt{n\log n} )$ Space ) ，shadowice1984( $O( m\sqrt{n\log n} )$ Time ，$O( n\log n )$ Space )，zx2003( $O( m\sqrt{n} )$ Time ，$O( n )$ Space )

Data：nzhtl1477( partially uploaded )

对于 $100\%$ 的数据，$1\leq n,m\leq 10^5$，$0\leq a_i\leq 10^9$。