Sequence Sets and Minimum Query Operations

You are given a positive integer n and m, and an integer sequence \(a_1,a_2,\dots,a_n\). Initially, you maintain n sets \(S_1, S_2, \dots, S_n\) where \(S_i = \{i\}\) for \(1 \leq i \leq n\).

Then you have to process exactly m operations. Each operation is one of the following types:

• 0 x y: Remove element \(y\) from set \(S_x\). It is guaranteed that \(y \in S_x\) at this moment.
• 1 x: Print the value \(\min_{i\in S_x} a_i\). It is guaranteed that \(S_x\) is nonempty at this moment.
• 2 x y: Merge the set \(S_y\) into \(S_x\) (i.e. set \(S_x = S_x \cup S_y\)) and then clear \(S_y\). It is guaranteed that both \(S_x\) and \(S_y\) are nonempty at the time of the operation, and after this operation, no further operation will involve set \(S_y\).
• 3 x y z: Update the value of \(a_y\) to \(z\) (i.e. assign \(a_y=z\)). It is guaranteed that \(y \in S_x\) at this moment and \(z < a_y\).

You need to simulate these operations and output the answers for all query operations (type 1).

Note: This problem is a typical heap/template problem which requires careful simulation of set merges, element removals, and value updates.

inputFormat

The first line contains two positive integers n and m.

The second line contains n integers \(a_1, a_2, \dots, a_n\).

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

• 0 x y
• 1 x
• 2 x y
• 3 x y z

It is guaranteed that all operations are valid.

outputFormat

For each query operation of the form 1 x, output one line with the answer \(\min_{i\in S_x} a_i\).

sample

3 5
5 3 7
1 1
3 1 1 2
1 1
2 1 2
1 1

5
2
2