AT_arc072_d [ARC072F] Dam

题目描述

你负责管理一个最多能储存 $L$ 升水的水库。一开始，水库是空的。接下来 $n$ 天，第 $i$ 天早上，有 $v$ 升 $t_i$ ℃ 的水会流进来；每天晚上，你可以决定要放多少水，但你必须保证第二天水不会溢出。水不会蒸发，温度也和流进水之外的因素无关。$v_1$ 升 $t_1$ ℃ 的水与 $v_2$ 升 $t_2$ ℃ 的水混合后的温度为 $\dfrac {t_1v_1+t_2v_2}{v_1+v_2}$。对于第 $i (i \in [1,n] \cap \mathbb N)$ 天，你需要求出最后水库是满的的情况下能达到的最高水温。不同日期的答案相互独立。

输入格式

输入按以下格式：

$$n \ L \\ t_1 \ v_1 \\ t_2 \ v_2 \\ \cdots \\ t_n \ v_n$$

输出格式

输出 $n$ 行，第 $i$ 行一个实数表示第 $i$ 天的答案。你的答案与标准答案的相对误差或绝对误差小于 $10^{-6}$ 即为正确。

输入输出样例 #1

输入 #1

3 10
10 10
20 5
4 3

输出 #1

10.0000000
15.0000000
13.2000000

输入输出样例 #2

输入 #2

4 15
0 15
2 5
3 6
4 4

输出 #2

0.0000000
0.6666667
1.8666667
2.9333333

输入输出样例 #3

输入 #3

4 15
1000000000 15
9 5
8 6
7 4

输出 #3

1000000000.0000000
666666669.6666666
400000005.0000000
293333338.8666667

说明/提示

• $1 \le n \le 5 \times 10^5$

• $1 \le L \le 10^9$

• $\forall i \in [1,n], 0 \le t_i \le 10^9, 1 \le v_i \le L,v_1=L$

• 所有数据都是整数。