多重集查询

题目描述

高桥君有很多什么都没写的球,以及一个袋子。初始时袋子是空的。高桥君将进行 $Q$ 次操作,每次操作是以下三种类型之一。

• 类型 $1$:在空白的球上写上整数 $X_i$,并放入袋子中。
• 类型 $2$:对于袋子中的每个球,把上面写的整数替换为该整数加上 $X_i$。
• 类型 $3$:取出袋子中整数最小的球(如果有多个这样的球,取出其中一个)。记录该球上写的整数,然后将其丢弃。

对于每个 $1\le i\le Q$,给出第 $i$ 次操作的类型 $P_i$,以及当操作类型为 $1$ 或 $2$ 时的 $X_i$ 的值。按顺序输出类型 $3$ 操作中记录的整数。

输入格式

输入按以下格式从标准输入给出:

$Q$
$query_1$
$query_2$
$:$
$query_Q$

第 $2$ 到第 $Q+1$ 行中,每个 $query_i$ 的格式如下:

$1$ $X_i$

$2$ $X_i$

$3$

每行的第一个数字是操作类型 $P_i$,满足 $1 \le P_i \le 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$ 位整数范围。

数据范围

• $1 \le Q \le 2\times 10^5$
• $1 \le P_i \le 3$
• $1 \le X_i \le 10^9$
• 输入均为整数。
• 存在至少一个 $i$ 使得 $P_i=3$。
• 若 $P_i=3$,则第 $i$ 次操作前袋子中至少有一个球。