题目描述

我们有一个空序列 $A$。需要按顺序处理 $Q$ 个查询，每个查询是以下三种类型之一：

1. 追加操作 1 x：将元素 $x$ 添加到 $A$ 的末尾。
2. 弹出操作 2：输出 $A$ 的第一个元素并删除它。保证执行此查询时 $A$ 不为空。
3. 排序操作 3：将此时的 $A$ 按升序排序。

输入格式

第一行输入 $Q$，表示查询数量。
接下来 $Q$ 行，每行一个查询：

• 1 x（追加 $x$）
• 2（弹出首元素）
• 3（排序）

输出格式

对于每个 2 类型查询，输出一行，包含被删除的元素。

样例

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

1
2

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

5
3
5

提示

样例1解释

1. 初始状态：A=[]
2. 依次追加后：A=[4,3,2,1]
3. 排序后：A=[1,2,3,4]
4. 弹出首元素 1，剩余 A=[2,3,4]
5. 追加 0：A=[2,3,4,0]
6. 弹出首元素 2，剩余 A=[3,4,0]

数据范围

• $1 \leq Q \leq 2 \times 10^5$
• $0 \leq x \leq 10^9$
• 输入中的所有值均为整数。