2714

2714. 左偏树

题目

你需要维护一个小根堆的集合，初始时集合是空的。

该集合需要支持如下四种操作：

1. 1 a，在集合中插入一个新堆，堆中只包含一个数 $a$。
2. 2 x y，将第 $x$ 个插入的数和第 $y$ 个插入的数所在的小根堆合并。数据保证两个数均未被删除。若两数已在同一堆中，则忽略此操作。
3. 3 x，输出第 $x$ 个插入的数所在小根堆的最小值。数据保证该数未被删除。
4. 4 x，删除第 $x$ 个插入的数所在小根堆的最小值（若最小值不唯一，则优先删除先插入的数）。数据保证该数未被删除。

输入格式

第一行包含整数 $n$，表示总操作数量。

接下来 $n$ 行，每行包含一个操作命令，形式如题所述。

输出格式

对于每个操作 $3$，输出一个整数，占一行，表示答案。

数据范围

$1 \le n \le 2 \times 10^5$,

$1 \le a \le 10^9$,

$1 \le x,y \le$ 当前插入数的个数。

数据保证所有操作合法。

输入样例：

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

输出样例：

2
3

题解