题目描述

Takahashi 有很多没有写任何东西的球，还有一个袋子。初始时，袋子是空的。Takahashi 将进行 $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$，按照记录的整数分别打印在一行上。

示例输入1

5
1 3
1 5
3
2 2
3

示例输出1

3
7

Takahashi 将执行以下操作。

• 在一个球上写 $3$ 并将其放入袋子中。
• 在一个球上写 $5$ 并将其放入袋子中。
• 现在袋子里有一个写着 $3$ 的球和一个写着 $5$ 的球。拿起其中较小的球，即 $3$。记录 $3$ 并扔掉它。
• 现在袋子中只有一个写着 $5$ 的球。将此整数替换为 $5+2=7$。
• 现在袋子中只有一个写着 $7$ 的球。拿起这个球，记录 $7$ 并扔掉它。

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

示例输入2

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

示例输出2

5000000000

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