問題文

• ＜お詫び＞

test3.txt に制約範囲外の値が含まれていたため、該当テストケースを削除いたしました。申し訳ございません。

$1$ つの空のお皿があります。

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

• 1 x k : お皿に重さ $x$ の木の実を $k$ 個追加する。
• 2 x : お皿にある重さ $x$ の木の実をすべて削除する。このとき、お皿に重さ $x$ の木の実がない場合は何も行わない。
• 3 y : 合計の重さが $y$ を超えないように木の実をお皿から取ることができるとき、取ることのできる木の実の個数の最大値を出力する。

制約

• $1 \leq Q \leq 10^5$
• $1 \leq x \leq 10^9$
• $1 \leq k \leq 10^4$
• $1 \leq y \leq 10^{18}$
• 入力はすべて整数である。

入力

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

$i \: (1 \leq i \leq Q)$ 番目の query $i$ では、まずクエリの種類 $t_i$ $(1, 2, 3$ のいずれか$)$ が与えられ、 $t_i = 1$ のときは追加で $x, k$、$t_i = 2$ のときは追加で $x$、$t_i = 3$ のときは追加で $y$ が与えられる。
すなわち、各クエリは以下に示す $3$ つの形式のいずれかが与えられる。

出力

$t_i = 3$ を満たすクエリの個数を $q$ として、$q$ 行出力せよ。
$j \: (1 \leq j \leq q)$ 行目では $j$ 番目のそのようなクエリに対する答えを出力せよ。

入出力例

8
1 2 2
1 3 1
1 5 2
3 6
3 7
2 3
3 7
3 15

2
3
2
4

$3$ 番目のクエリが処理された時点で、お皿には重さ $2$ の木の実が $2$ つ、重さ $3$ の木の実が $1$ つ、重さ $5$ の木の実が $2$ つあります。
$4$ 番目のクエリについて、例えば、重さ $2$ の木の実を $1$ つ、重さ $3$ の木の実を $1$ つ取ることによって $2$ つの木の実を取ることができます。
$5$ 番目のクエリについて、例えば、重さ $2$ の木の実を $2$ つ、重さ $3$ の木の実を $1$ つ取ることによって $3$ つの木の実を取ることができます。
$6$ 番目のクエリでは、重さ $3$ の木の実がすべて削除されます。
$7$ 番目のクエリについて、例えば、重さ $2$ の木の実を $1$ つ、重さ $5$ の木の実を $1$ つ取ることによって $2$ つの木の実を取ることができます。
$8$ 番目のクエリについて、お皿にあるすべての木の実を取ることができるため、$4$ つの木の実を取ることができます。

12
3 10528605371295668
1 647067399 4040
3 2118234349761
2 647067399
1 407923686 5016
1 509459218 6931
3 1504393153494
1 394517113 1774
1 856989481 3418
1 351851508 9638
3 8182099199625
2 509459218

0
3273
3687
20441