题目描述

小高有许多球和一个袋子。最初，袋子是空的。小高将进行 $Q$ 次操作，每次操作是以下三种类型之一。

1. 在一个空白球上写上整数 $X_i$ 并将其放入袋中。

2. 对于袋中的每个球，将其上写的整数替换为该整数加上 $X_i$。

3. 从袋中取出写有最小整数的球（如果有多个这样的球，取出其中一个）。记录这个球上的整数并将其丢弃。

对于每个类型为 3 的操作，请按顺序输出记录的整数。

输入格式

输入格式如下：

$Q$

$query_1$

$query_2$

$\vdots$

$query_Q$

每个 $query_i$ 的格式如下三者之一：

• $1$ $X_i$

• $2$ $X_i$

• $3$

第一个数字是 $1 \leq P_i \leq 3$，表示操作类型。如果 $P_i=1$ 或 $P_i=2$，后面会跟一个空格和 $X_i$。

输出格式

对于每个 $P_i=3$ 的操作，在单独的一行中输出记录的整数。

样例

5
1 3
1 5
3
2 2
3

3
7

6
1 1000000000
2 1000000000
2 1000000000
2 1000000000
2 1000000000
3

5000000000

样例解释

【样例说明1】

小高将进行以下操作：

1. 在一个球上写3并放入袋中。

2. 在一个球上写5并放入袋中。

3. 袋中现在有一个写着3的球和一个写着5的球。取出较小的那个，即3。记录3并丢弃。

4. 袋中现在只有一个写着5的球。将这个整数替换为5+2=7。

5. 袋中现在只有一个写着7的球。取出这个球，记录7，并丢弃。

因此，我们应该按顺序输出3和7。

【样例说明2】

注意输出可能不适合32位整数。

数据范围

• $1 \leq Q \leq 2\times 10^5$
• $1 \leq P_i \leq 3$
• $1 \leq X_i \leq 10^9$
• 所有输入都是整数。
• 至少有一个 $i$ 满足 $P_i=3$。
• 如果 $P_i=3$，那么在第 $i$ 次操作之前袋中至少有一个球。

来源

• AtCoder ABC212D