排序查询

题目描述

我们有一个空序列 $A$。给定 $Q$ 个查询，按给出顺序处理。每个查询是以下三种之一：

1 x：把 $x$ 追加到 $A$ 的末尾。

2：输出 $A$ 开头的元素，然后删除该元素。保证给出该查询时 $A$ 非空。

3：将 $A$ 按升序排序。

输入格式

输入按以下格式从标准输入给出：

$Q$
$\mathrm{query} 1$
$\mathrm{query} 2$
$\vdots$
$\mathrm{query} Q$

第 $i$ 个查询 $\mathrm{query} i$ 以查询类型 $c_i$（$1$、$2$ 或 $3$）开头。 如果 $c_i=1$，该行还包含一个整数 $x$。

换句话说，每个查询是以下三种格式之一：

1 x

2

3

输出格式

设 $q$ 为 $c_i=2$ 的查询个数，输出 $q$ 行。

第 $j$ 行 $(1 \le j \le q)$ 输出第 $j$ 个此类查询的答案。

样例

8
1 4
1 3
1 2
1 1
3
2
1 0
2

1
2

下面第 $i$ 行表示样例输入 $1$ 中第 $i$ 个查询处理完后 $A$ 的内容。

$(4)$

$(4,3)$

$(4,3,2)$

$(4,3,2,1)$

$(1,2,3,4)$

$(2,3,4)$

$(2,3,4,0)$

$(3,4,0)$

9
1 5
1 5
1 3
2
3
2
1 6
3
2

5
3
5

下面第 $i$ 行表示样例输入 $2$ 中第 $i$ 个查询处理完后 $A$ 的内容。

$(5)$

$(5,5)$

$(5,5,3)$

$(5,3)$

$(3,5)$

$(5)$

$(5,6)$

$(5,6)$

$(6)$

数据范围

• $1 \le Q \le 2 \times 10^5$
• $0 \le x \le 10^9$
• 给出类型 2 的查询时 $A$ 非空。
• 输入中的所有值均为整数。