/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 400 点
問題文
高橋君は何も書かれていないたくさんのボールと 1 つの袋を持っています。 最初、袋は空で、高橋君は Q 回の操作を行います。 それぞれの操作は以下の 3 種類のうちのいずれかです。
- 操作 1 : まだ何も書かれていないボール 1 つに整数 X_i を書き込み、袋に入れる。
- 操作 2 : 袋に入っているすべてのボールについて、そこに書かれている数を、それに X_i を加えたものに書き換える。
- 操作 3 : 袋に入っているボールのうち書かれている数が最小のもの（複数ある場合はそのうちの 1 つ）を取り出し、そこに書かれている数を記録する。その後、そのボールを捨てる。
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
- 入力は全て整数である。
- P_i=3 であるような i が 1 つ以上存在する。
- P_i=3 であるとき、 i 回目の操作の直前の時点で、袋には 1 つ以上のボールが入っている。
入力
入力は以下の形式で標準入力から与えられる。
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 bit整数に収まらないことがある事に注意してください。
Score : 400 points
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.