Heap Merge and Delete Operations

You are given (n) initial min-heaps, where each heap contains exactly one number. The heaps are 1-indexed by the order in which the numbers are given. You need to process (q) operations of the following two types:

1. 1 x y: Merge the min-heaps containing the (x)-th and (y)-th number. If either the (x)-th or (y)-th number has already been deleted, or if they are already in the same heap, ignore this operation.
   
   
2. 2 x: Find the minimum number in the min-heap that contains the (x)-th number and output it, then delete that minimum number from the heap. If there are several numbers equal to the minimum, delete the one that was input earlier. If the (x)-th number has already been deleted, output (-1) and ignore the deletion.
   
   In other words, if a heap contains elements (a_1, a_2, \dots, a_k) (with their original order used to break ties when values are equal), a query of type 2 should output (\min{a_1,a_2,\dots,a_k}) (with the tie broken by the order of input) and remove that element from the heap.

inputFormat

The first line contains two integers (n) and (q) separated by a space, representing the number of initial heaps and the number of operations, respectively.

The second line contains (n) integers (a_1, a_2, \cdots, a_n), where (a_i) is the number in the (i)-th heap.

Each of the next (q) lines contains an operation in one of the two formats:

• 1 x y: Merge the heaps that contain the \(x\)-th and \(y\)-th numbers.
• 2 x: Output and delete the minimum number from the heap that contains the \(x\)-th number.

outputFormat

For each operation of type 2, output the corresponding number on a new line. If the (x)-th number in a query of type 2 is already deleted, output (-1) for that query.

sample

5 6
4 3 5 2 1
1 1 2
2 2
1 3 5
2 3
2 1
2 4

3
1
4
2