ストーリー

「...好きです」

いろはちゃんから帰り道にもらった、一通の封筒。かわいらしいハートのシールで封がしてある。 中にはこんな問題が入っていた。
「いろはちゃん、やっぱ君が本当のラスボスだな...」

問題文

※ひらきちとはこのコンテストを主催した人の名前である。また、ひらきちくんはいろはちゃんではない。

いろは界では、いろはちゃんが数直線上に数十万個のコインを置いたり消したりするのは、有名な話です。

最初、数直線上には一つもコインがありません。
いろはちゃんは、Q 回の操作を順に行います。操作は以下の 3 種類があります。

• 追加の術：数直線上の座標 x に v 円のコインを置く。ただし、座標 x にはこの時点でコインが一個も置かれていないことが保証されている。
• 消去の術：数直線上の座標 x にあるコインを消す。ただし、座標 x にはこの時点でコインが置かれていることが保証されている。
• 命令の術：ひらきちくんを座標 x に置き、コインを一個取らせる。この時ひらきちくんは、「効率」が最大となるようなコインを必ず取る。なお、座標 c にある w 円のコインを取る時の「効率」は \frac{w}{|c-x|} である。そこでは、|t| は t の絶対値である。

例えば、座標 2 に 3 円 のコイン、座標 5 に 8 のコインがある場合、各場合における効率の最大値は以下のようになります。

• ひらきちくんが座標 0 に置く場合、ひらきちくんは「効率」が最大となる座標 5 にあるコインを取り、「効率」の値は 1.6
• ひらきちくんが座標 1 に置く場合、ひらきちくんは「効率」が最大となる座標 2 にあるコインを取り、「効率」の値は 3.0
• ひらきちくんが座標 7 に置く場合、ひらきちくんは「効率」が最大となる座標 5 にあるコインを取り、「効率」の値は 4.0

ただし、命令の術で取られたコインはいろはちゃんの手腕によってすぐ元の場所に戻されるため、同じコインを二度以上ひらきちくんが取ることは有り得るということに注意してください。

各命令の術について、ひらきちくんの動きにおける「効率」の値を順に求めてください。
ただし、命令の術において、その時点で数直線上にコインが存在しない場合は「効率」の値が 0 となります。

制約

• 入力はすべて整数
• 1\leq Q\leq3 \times 10^5
• 0\leq x\leq10^9
• 0\leq v\leq10^9
• 全ての追加の術において、コインを追加する座標にはその時点でコインが置かれていない
• 全ての消去の術において、コインを消去する座標にはその時点でコインが置かれている
• 全ての命令の術において、ひらきちくんのいる座標にその時点でコインが置かれていない

部分点

この問題では、部分点が以下のように存在します。

• Q \leq 120000 を満たすテストケース全てに正解すると、1100 点が与えられる。
• 全てのテストケースに正解すると、さらに 300 点が与えられる。

入力例 1

11
1 2 3
3 10
1 5 8
3 0
3 1
3 7
2 2
1 7 9
3 3
3 6
3 10

出力例 1

0.375000000000
1.600000000000
3.000000000000
4.000000000000
4.000000000000
9.000000000000
3.000000000000

入力例 2

10
1 0 10
3 1
3 2
3 3
3 4
3 5
3 6
3 7
3 8
3 9

出力例 2

10.000000000000
5.000000000000
3.333333333333
2.500000000000
2.000000000000
1.666666666667
1.428571428571
1.250000000000
1.111111111111

解説

解説