You are given a graph where each vertex has a weight. Initially, there are no edges.

There are three types of operations:

1. Add an undirected edge between $x$ and $y$.
2. Revert the graph to the state after the $x$-th operation (note that $x$ can be $0$, which means reverting to the initial state).
3. Query the $y$-th smallest vertex weight among all vertices reachable from $x$ in the same connected component. If it does not exist, output $-1$.

Input

The first line contains two integers $n$ and $m$, representing the number of vertices and the number of operations, respectively.

The next line contains $n$ integers, representing the weight of each vertex.

The following $m$ lines each describe an operation in one of the following formats:

1 x y

2 x

3 x y

The meanings are as described above.

Output

For each operation of type 3, output a single integer on a new line representing the answer.

Examples

Input 1

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 1

94271893
223885531

Subtasks

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)

For $100\%$ of the data, $1\leq n,m\leq 10^5$, $0\leq a_i\leq 10^9$.