题目描述

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

1. 在一个空白球上写上整数 $X_i$ 并将其放入袋中。
2. 对于袋中的每个球，将其上写的整数替换为该整数加上 $X_i$。
3. 从袋中取出写有最小整数的球（如果有多个这样的球，取出其中一个）。记录这个球上的整数并将其丢弃。

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

输入格式

输入格式如下：

$Q$

$query_1$

$query_2$

$:$

$query_Q$

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

$1$ $X_i$

$2$ $X_i$

$3$

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

输出格式

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

输入输出样例 #1

输入 #1

5
1 3
1 5
3
2 2
3

输出 #1

3
7

输入输出样例 #2

输入 #2

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

输出 #2

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$ 次操作之前袋中至少有一个球。