AT_abc212_d [ABC212D] Querying Multiset

[problemUrl]: https://atcoder.jp/contests/abc212/tasks/abc212_d 高橋君は何も書かれていないたくさんのボールと $ 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 $ であるような各操作について、記録された数を改行区切りで出力せよ。

### 制約 - $ 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整数に収まらないことがある事に注意してください。