Score : $400$ points

问题描述

Takahashi有许多空白的球和一个袋子。最初，袋子是空的。Takahashi将执行$Q$次操作，每次操作属于以下三种类型之一。

• 类型 $1$: 在一个空白球上写入整数$X_i$，然后将其放入袋子中。
• 类型 $2$: 对于袋子中的每个球，用该球上所写的整数加上$X_i$来替换它。
• 类型 $3$: 拿起袋子里整数最小的那个球（如果有多个这样的球，取出其中一个）。记录这个球上所写的整数并将其丢弃。

对于每个$1\leq i\leq Q$，已知第$i$次操作的类型$P_i$以及如果该操作是类型$1$或$2$时的$X_i$值。按照顺序打印出类型$3$操作所记录的整数。

以上为通义千问 qwen-max 翻译，仅供参考。

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.

update @ 2024/3/10 09:27:25