D - 查询多重集合

分数：400分

问题描述

高田有许多没有写任何东西的球和一个袋子。起初，袋子是空的。高田将执行Q个操作，每个操作都是以下三种类型之一。

• 类型1：在一个空白球上写下一个整数$X_i$，然后放入袋子中。
• 类型2：对于袋子中的每个球，用该球上写的整数加上$X_i$来替换它。
• 类型3：从袋子中取出最小整数的球（如果有多个球，则取其中之一）。记录此球上的整数，并将其丢弃。

对于每个$1\leq i\leq Q$，给定第$i$个操作的类型$P_i$，以及如果操作是类型1或类型2，则给出$X_i$的值。按顺序打印类型3操作中记录的整数。

约束

• $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$个操作之前，袋子里至少有一个球。

---

输入

从标准输入获取输入数据，格式如下：

$Q$

$query_1$

$query_2$

$:$

$query_Q$

第$2$行到第$(Q+1)$行的每个$query_i$的格式如下：

``` $1$ $X_i$ ``` ``` $2$ $X_i$ ``` ``` $3$ ```

每行的第一个数为$1\leq P_i\leq 3$，表示操作的类型。 如果$P_i=1$或$P_i=2$，则后面跟着一个空格，然后跟着$X_i$。

输出

对于$Q$个操作中$P_i=3$的每个操作，按照记录的顺序，每行输出一个整数。

---

5
1 3
1 5
3
2 2
3

3
7

高田将执行以下操作。

• 在一个球上写$3$，然后放入袋子中。
• 在一个球上写$5$，然后放入袋子中。
• 袋子现在有一个写有$3$的球和一个写有$5$的球。取出其中较小的球，即$3$。记录并丢弃$3$。
• 袋子现在仅有一个写有$5$的球。将该整数替换为$5+2=7$。
• 袋子现在仅有一个写有$7$的球。取出此球，记录$7$并丢弃。

因此，应按照记录的顺序打印$3$和$7$。

---

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

5000000000

请注意，输出可能不能容纳在$32$位整数中。