Background

Thanks to

ing the first version of the testdata generator.

gen。

Problem Description

Given positive integers $n$ and $m$, and an integer sequence $a_{1,\dots,n}$ of length $n$.

You need to maintain the sequence $a_{1,\dots,n}$ and $n$ sets $S_{1,\dots,n}$. Initially, $S_i=\{i\}$.

Then you will perform the following four types of operations for a total of $m$ times. Each operation is in one of these forms:

• 0 x y: Delete element $y$ from set $S_x$. It is guaranteed that $y$ is in $S_x$ at this moment.
• 1 x: Query $\min_{i\in S_x} a_i$. It is guaranteed that $S_x$ is non-empty at this moment.
• 2 x y: Merge set $S_y$ into $S_x$ and clear $S_y$. It is guaranteed that both $S_x$ and $S_y$ are non-empty at this moment, and after this operation there will be no further operations involving set $S_y$.
• 3 x y z: Assign $a_y$ to be $z$. It is guaranteed that $y$ is in $S_x$ at this moment, and $z<a_y$.

It is not hard to see that this is a heap template problem, so please finish it now.

Input Format

The first line contains two positive integers $n$ and $m$.

The second line contains $n$ positive integers; the $i$-th positive integer is $a_i$.

The next $m$ lines each contain one operation as described above.

Output Format

For each operation 1, output one integer per line (note that it is not guaranteed to remain positive) as the answer.

5 5
1 2 3 4 4
2 4 5
3 4 5 3
1 4
0 4 5
1 4

3
4

Hint

For $20\%$ of the data, $n=m=10$.

For $80\%$ of the data, $n=m=10^5$.

For $100\%$ of the data, $1\le n,m\le10^6$, $1\le a_i\le2\times10^9$. It is guaranteed that at any time, the absolute value of any element in any heap does not exceed $10^{15}$ (in plain words: each operation 3 decreases a single value by at most $5\times10^8$).

---

For the last two test points, the setter’s handwritten heap and the pairing heap in pbds both ran in a few hundred milliseconds. If you are getting constant-factor TLE, you can message privately.

Translated by ChatGPT 5