该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

双端优先队列（Double-Ended Priority Queue）

问题描述

给定一个多重集 $S = \{S_1, \dots, S_N\}$。请按顺序处理以下 $Q$ 个查询：

• 0 x：将 $x$ 加入 $S$。
• 1：输出 $S$ 中的一个最小元素，并将其从 $S$ 中删除。
• 2：输出 $S$ 中的一个最大元素，并将其从 $S$ 中删除。

题目保证：在处理类型 1 和 2 的查询时，$S$ 非空。

约束条件

• $0 \leq N \leq 5 \times 10^5$
• $1 \leq Q \leq 5 \times 10^5$
• $-1 \times 10^9 \leq S_i, x \leq 10^9$

输入格式

$N\ Q$
$S_1\ \cdots\ S_N$
$Query_0$
:
$Query_{Q-1}$

4 10
-3 0 1 3
0 3
2
2
0 -2
0 1
1
1
2
1
2

3
3
-3
-2
1
0
1