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

5
1 3
1 5
3
2 2
3

3
7

高橋君は次のように操作を行います。

• $3$ の書かれたボールを袋に入れる。
• $5$ の書かれたボールを袋に入れる。
• 今、袋には $3$ の書かれたボールと $5$ の書かれたボールが入っているため、このうち小さい $3$ の書かれたボールを取り出し、 $3$ を記録した後に捨てる。
• 今、袋には $5$ の書かれたボールのみが入っているため、この数を $5+2=7$ に書き換える。
• 今、袋には $7$ の書かれたボールのみが入っているため、このボールを取り出し、 $7$ を記録した後に捨てる。

よって、記録された順に $3$ , $7$ を出力します。

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

5000000000

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