Graph Rollback and K-th Smallest Query

You are given an undirected graph with n vertices. Each vertex has a weight. Initially, the graph has no edges, i.e. every vertex is isolated.

You need to process m operations. There are three types of operations:

1. Add an undirected edge between vertices \(x\) and \(y\).
2. Rollback the graph to the state after the \(x\)-th operation (\(x=0\) means rolling back to the initial state).
3. Query: For the connected component containing vertex \(x\), output the \(y\)-th smallest vertex weight. If the component has fewer than \(y\) vertices, output -1.

Note: The operations are 1-indexed. When merging two connected components, consider the union of their vertices and sort their weights in non-decreasing order. For query operations, the \(k\)-th smallest element is the one at index \(k-1\) after sorting.

The input and output formats are described below.

inputFormat

The first line contains two integers n and m — the number of vertices and the number of operations.

The second line contains n integers, where the \(i\)-th integer is the weight of vertex \(i\>.

Then m lines follow. Each line represents an operation in one of the following formats:

• 1 x y: Add an undirected edge between vertices \(x\) and \(y\).
• 2 x: Rollback to the state after the \(x\)-th operation (if \(x=0\), rollback to the initial state).
• 3 x y: Query the connected component containing vertex \(x\) for the \(y\)-th smallest weight. Output the answer on a new line.

outputFormat

For each query operation (type 3), output the answer (the \(y\)-th smallest weight in the connected component of vertex \(x\) or -1 if it does not exist) on a new line.

sample

4 6
10 20 30 40
3 1 1
1 1 2
3 2 2
1 3 4
3 3 1
2 1

10
20
30