题目背景

感谢

版数据生成器。

gen。

题目描述

给定正整数 $n$ 和 $m$ 以及一个长为 $n$ 的整数序列 $a_{1,\dots,n}$。

你需要维护序列 $a_{1,\dots,n}$ 以及 $n$ 个集合 $S_{1,\dots,n}$，初始时 $S_i=\{i\}$。

接下来要进行以下四种操作共 $m$ 次，每次操作形如：

• 0 x y：表示将元素 $y$ 从集合 $S_x$ 中删去。保证此时元素 $y$ 在集合 $S_x$ 中。
• 1 x：表示询问 $\min_{i\in S_x} a_i$，保证此时集合 $S_x$ 非空。
• 2 x y：将集合 $S_y$ 中并入 $S_x$ 并清空集合 $S_y$。保证此时集合 $S_x,S_y$ 均非空，且此次操作后不会再出现涉及集合 $S_y$ 的操作。
• 3 x y z：表示将 $a_y$ 赋值为 $z$。保证此时元素 $y$ 在集合 $S_x$ 中，且 $z<a_y$。

不难发现这是一道堆的模板题，所以现在请你完成它。

输入格式

第一行两个正整数 $n$ 和 $m$。

第二行 $n$ 个正整数，第 $i$ 个正整数表示 $a_i$。

接下来 $m$ 行每行一个操作如题。

输出格式

对于每个 1 操作一行整数（注意不保证依然为正）表示答案。

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

3
4

提示

对于 $20\%$ 的数据，$n=m=10$；

对于 $80\%$ 的数据，$n=m=10^5$；

对于 $100\%$ 的数据，$1\le n,m\le10^6$，$1\le a_i\le2\times10^9$，保证任意时刻任意堆中元素绝对值不超过 $10^{15}$（人话：保证每次 3 操作最多单点减 $5\times10^8$）。

---

最后两个点出题人的手写堆和 pbds 的配对堆都跑到了几百毫秒，如果有被卡常的可私。