102123: [AtCoder]ABC212 D - Querying Multiset

Problem Statement

Takahashi has many balls, on which nothing is written, and one bag. Initially, the bag is empty. Takahashi will do $Q$ operations, each of which is of one of the following three types.

• Type $1$: Write an integer $X_i$ on a blank ball and put it in the bag.
• Type $2$: For each ball in the bag, replace the integer written on it with that integer plus $X_i$.
• Type $3$: Pick up the ball with the smallest integer in the bag (if there are multiple such balls, pick up one of them). Record the integer written on this ball and throw it away.

For each $1\leq i\leq Q$, you are given the type $P_i$ of the $i$-th operation and the value of $X_i$ if the operation is of Type $1$ or $2$. Print the integers recorded in the operations of Type $3$ in order.

Constraints

• $1 \leq Q \leq 2\times 10^5$
• $1 \leq P_i \leq 3$
• $1 \leq X_i \leq 10^9$
• All values in input are integers.
• There is one or more $i$ such that $P_i=3$.
• If $P_i=3$, the bag contains at least one ball just before the $i$-th operation.

Input

Input is given from Standard Input in the following format:

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

Each $query_i$ in the $2$-nd through $(Q+1)$-th lines is in the following format:

$1$ $X_i$

$2$ $X_i$

$3$

The first number in each line is $1\leq P_i\leq 3$, representing the type of the operation. If $P_i=1$ or $P_i=2$, it is followed by a space, and then by $X_i$.

Output

For each operation with $P_i=3$ among the $Q$ operations, print the recorded integer in its own line.

Sample Input 1

5
1 3
1 5
3
2 2
3

Sample Output 1

3
7

Takahashi will do the following operations.

• Write $3$ on a ball and put it in the bag.
• Write $5$ on a ball and put it in the bag.
• The bag now contains a ball with $3$ and another with $5$. Pick up the ball with the smaller of them, or $3$. Record $3$ and throw it away.
• The bag now contains just a ball with $5$. Replace this integer with $5+2=7$.
• The bag now contains just a ball with $7$. Pick up this ball, record $7$, and throw it away.

Therefore, we should print $3$ and $7$, in the order they are recorded.

Sample Input 2

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

Sample Output 2

5000000000

Note that the outputs may not fit into a $32$-bit integer.

问题描述

高桥明有许多空白的球和一个袋子。最初，袋子是空的。高桥明将进行$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

高桥明将执行以下操作。

• 在球上写下一个数字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位整数中。