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

仓库取货

题目描述

仓库最初为空，每件货物都有一个整数估值。依次执行 $Q$ 次操作，操作分为三类：

• 1 X：放入一件估值为 $X$ 的新货物。
• 2 X：将此时仓库中每件货物的估值都增加 $X$。仓库为空时，这次操作没有影响。
• 3：取出当前估值最大的一件货物，输出它的估值，并将这件货物移出仓库。若有多件并列最大，只取出其中一件。

整体增加估值只作用于当时已经在仓库中的货物，不影响以后入库的新货物。请按操作顺序输出每次取货的估值。

输入格式

第一行输入整数 $Q$，其中 $1\le Q\le2\times10^5$。

接下来 $Q$ 行，每行是 1 X、2 X 或 3。对于前两种操作，$1\le X\le10^9$。

所有输入值均为整数。保证至少有一次 3 操作，且执行每次 3 操作前仓库均非空。相同估值的货物允许重复入库。

输出格式

对每次 3 操作输出一行一个整数，表示本次取出的货物估值。

输入输出样例

输入 #1

7
1 4
1 9
2 3
3
1 10
3
3

输出 #1

12
10
7

输入 #2

3
2 5
1 2
3

输出 #2

2

输入 #3

5
1 1000000000
2 1000000000
2 1000000000
2 1000000000
3

输出 #3

4000000000

样例说明

样例 1 中，第一次整体增加后两件货物的估值为 $7,12$，先取出 $12$。新入库货物的估值为 $10$，之后依次取出 $10,7$。样例 2 的第一次操作发生在空仓库中，不能把这次增加记到以后入库的货物上。