配点 : $900$ 点

問題文

あなたはダムを管理しています。ダムは $L$ リットルまで水を蓄えることができます。ダムははじめ干からびています。また、毎日夜に好きな量の水を排出することができます。毎日朝にはダムに水が流入しますが、その時水が溢れないようにする必要があります。

$i$ 日目の朝には $t_i$ 度の水が $v_i$ リットル流入することがわかっています。 各日について、あなたはその日の昼にダムにちょうど $L$ リットルの水がたまっているという条件のもと、その時点でのダムの水温を最大化しようとすると何度になるかふと気になりました。各 $i$ について水温の最大値を求めてください。ここで、各最大化のための水の排出は独立に考えるものとします。すなわち、$i$ 日目の水温の最大化のために排出する水の量は、$j( \neq i)$ 日目の水温の最大化のために排出する水の量と異なっていても構いません。

ただし、水温は流れてくる水以外の一切の影響を受けないものとします。特に、$T_1$ 度、$V_1$ リットルの水と $T_2$ 度、$V_2$ リットルの水が混ざると $\frac{T_1*V_1+T_2*V_2}{V_1+V_2}$ 度、$V_1+V_2$ リットルの水となり、これ以外で水の体積・温度が変化することはありません。

制約

• $1 \leq N \leq 5*10^5$
• $1 \leq L \leq 10^9$
• $0 \leq t_i \leq 10^9(1 \leq i \leq N)$
• $1 \leq v_i \leq L(1 \leq i \leq N)$
• $v_1 = L$
• $L, v_i, t_i$ は整数である

入力

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

$N$ $L$

$t_1$ $v_1$

$t_2$ $v_2$

:

$t_N$ $v_N$

出力

$i$ 日目の朝にダムに $L$ リットル蓄えることのできる水温の最大値を $i$ 行目に出力せよ。

答えは、相対誤差または絶対誤差が $10^{-6}$ 以下であれば許容される。

3 10
10 10
20 5
4 3

10.0000000
15.0000000
13.2000000

• $1$ 日目には $1$ 日目に流れ込んだ水のみがあるので、必ず$10$度です。
• $1$ 日目の夜に水を $5$ リットル捨て、$2$ 日目に流入する水と混ざると $10$ リットル、$15$ 度の水が $2$ 日目に蓄えられます。
• $1$ 日目の夜に水を $8$ リットル捨て、$2, 3$ 日目に流入する水と混ざると $10$ リットル、$13.2$度の水が $3$ 日目に蓄えられます。

4 15
0 15
2 5
3 6
4 4

0.0000000
0.6666667
1.8666667
2.9333333

4 15
1000000000 15
9 5
8 6
7 4

1000000000.0000000
666666669.6666666
400000005.0000000
293333338.8666667

水温は $100$ 度を超えることがありますが、蒸発については考えません。