配点 : $300$ 点

問題文

整数の多重集合 $S$ があります。はじめ $S$ は空です。

$Q$ 個のクエリが与えられるので順に処理してください。 クエリは次の $3$ 種類のいずれかです。

• 1 x : $S$ に $x$ を $1$ 個追加する。
• 2 x c : $S$ から $x$ を $\mathrm{min}(c,$ $(S$ に含まれる $x$ の個数 $))$ 個削除する。
• 3 : $(S$ の最大値 $)-$ $(S$ の最小値 $)$ を出力する。このクエリを処理するとき、 $S$ が空でないことが保証される。

制約

• $1 \leq Q \leq 2\times 10^5$
• $0 \leq x \leq 10^9$
• $1 \leq c \leq Q$
• 3 のクエリを処理するとき、$S$ は空でない。
• 入力は全て整数

入力

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

$Q$

$\mathrm{query}_1$

$\vdots$

$\mathrm{query}_Q$

$i$ 番目のクエリを表す $\mathrm{query}_i$ は以下の $3$ 種類のいずれかである。

$1$ $x$

$2$ $x$ $c$

$3$

出力

3 のクエリに対する答えを順に改行区切りで出力せよ。

8
1 3
1 2
3
1 2
1 7
3
2 2 3
3

1
5
4

多重集合 $S$ は以下のように変化します。

• $1$ 番目のクエリ : $S$ に $3$ を追加する。$S$ は $\lbrace3 \rbrace$ となる。
• $2$ 番目のクエリ : $S$ に $2$ を追加する。$S$ は $\lbrace2, 3\rbrace$ となる。
• $3$ 番目のクエリ : $S = \lbrace 2, 3\rbrace$ の最大値は $3$ 、最小値は $2$ なので、 $3-2=1$ を出力する。
• $4$ 番目のクエリ : $S$ に $2$ を追加する。$S$ は $\lbrace2,2,3 \rbrace$ となる。
• $5$ 番目のクエリ : $S$ に $7$ を追加する。$S$ は $\lbrace2, 2,3, 7\rbrace$ となる。
• $6$ 番目のクエリ : $S = \lbrace2,2,3, 7\rbrace$ の最大値は $7$ 、最小値は $2$ なので、 $7-2=5$ を出力する。
• $7$ 番目のクエリ : $S$ に含まれる $2$ の個数は $2$ 個なので、 $\mathrm{min(2,3)} = 2$ 個の $2$ を $S$ から削除する。$S$ は $\lbrace3, 7\rbrace$ となる。
• $8$ 番目のクエリ : $S = \lbrace3, 7\rbrace$ の最大値は $7$ 、最小値は $3$ なので、 $7-3=4$ を出力する。

4
1 10000
1 1000
2 100 3
1 10

クエリ $3$ が含まれない場合、何も出力してはいけません。