题目描述

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

$i$ 日目の朝には $t_i$ 度の水が $v_i$ リットル流入することがわかっています。 各日について、あなたはその日の昼にダムにちょうど $L$ リットルの水がたまっているという条件のもと、その時点でのダムの水温を最大化しようとすると何度になるかふと気になりました。各 $i$ について水温の最大値を求めてください。ここで、各最大化のための水の排出は独立に考えるものとします。すなわち、$i$ 日目の水温の最大化のために排出する水の量は、$j(≠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$ リットルの水となり、これ以外で水の体積・温度が変化することはありません。

输入格式

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

$N$ $L$ $t_1$ $v_1$ $t_2$ $v_2$ : $t_N$ $v_N$

输出格式

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

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

题目大意

有个水库，最多能存$L$单位水，一开始是空的

接下来$n$天，每天早上有$v_i$单位的，水温为$t_i$的水流进来

每天晚上你可以放掉一些水，多少自定。但是必须保证第二天水库不会溢出

现在问，对于每个$i$，在使用最优放水策略的情况下，第$i$天水库是满的情况下最高水温

（每一问之间互相独立）

混合后的温度计算:$t_3=\frac{t_1*v_1+t_2*v_2}{v_1+v_2}$

$0 \leq n \leq 5 * 10^5$,其他数int范围内

3 10
10 10
20 5
4 3

10.0000000
15.0000000
13.2000000

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

提示

制約

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

Sample Explanation 1

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

Sample Explanation 3

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