题目描述

高橋君は何も書かれていないたくさんのボールと $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$ において記録された数を順に出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$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$ であるような各操作について、記録された数を改行区切りで出力せよ。

题目大意

给定一个集合和 $Q$ 次操作，每个操作可能是以下操作之一：

• 第一个操作给定整数 $x$，表示将 $x$ 放入集合。

• 第二个操作给定整数 $x$，表示将集合的数分别加上 $x$。

• 第三个操作将集合最小的数删除。

对于每个第三个操作，输出你删去的数。

保证 $1\le Q\le2\times10^5$，操作种类 $op\in\{1,2,3\}$，$1\le x\le10^9$。

5
1 3
1 5
3
2 2
3

3
7

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

5000000000

提示

制約

• $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$ つ以上のボールが入っている。

Sample Explanation 1

高橋君は次のように操作を行います。 - $3$ の書かれたボールを袋に入れる。 - $5$ の書かれたボールを袋に入れる。 - 今、袋には $3$ の書かれたボールと $5$ の書かれたボールが入っているため、このうち小さい $3$ の書かれたボールを取り出し、 $3$ を記録した後に捨てる。 - 今、袋には $5$ の書かれたボールのみが入っているため、この数を $5+2=7$ に書き換える。 - 今、袋には $7$ の書かれたボールのみが入っているため、このボールを取り出し、 $7$ を記録した後に捨てる。 よって、記録された順に $3$ , $7$ を出力します。

Sample Explanation 2

答えが $32$ bit整数に収まらないことがある事に注意してください。