题目描述

你负责控制一座水坝。这座水坝最多可以储存$L$升水。初始时，水坝是空的。每天早上会有一定量的水流入水坝，而每天晚上则可以放出任意数量的水，但需要调整这个数量以确保第二天早上水坝不会溢出。

已知第$i$天早上会有$v_i$升温度为$t_i$摄氏度的水流入水坝。你想知道在每天中午时水坝中的水温可能达到的最高值，条件是水坝中必须恰好有$L$升水。对于每个$i$，找出第$i$天中午水坝中水温的最大可能值。这里，将每一天的最大化分开考虑，也就是说，用于最大化第$i$天的水温的放水量可能与用于最大化第$j$天的水温的放水量不同（$j≠i$）。

另外，假设水的温度仅受到流入水坝的新水的影响。也就是说，当$V_1$升温度为$T_1$摄氏度的水和$V_2$升温度为$T_2$摄氏度的水混合在一起时，它们会变成$V_1+V_2$升温度为$\frac{T_1\*V_1+T_2\*V_2}{V_1+V_2}$摄氏度的水，且水的体积和温度不受任何其他因素的影响。

约束条件

• $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$、每个$t_i$和$v_i$都是整数。

输入

输入以以下格式从标准输入给出：

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

输出

输出$N$行。第$i$行应包含最大温度，使得在第$i$天中午水坝中恰好可以储存$L$升水且水温为该温度。

如果绝对误差或相对误差不超过$10^{-6}$，则接受这些值。

示例输入1

3 10
10 10
20 5
4 3

示例输出1

10.0000000
15.0000000
13.2000000

• 在第一天，水坝中的水温始终为$10$摄氏度：第一天流入水坝的唯一一次水的温度。
• 第二天可以存储$10$升$15$摄氏度的水，方法是在第一天晚上放出$5$升水，并将剩下的水与第二天流入水坝的水混合。
• 第三天可以存储$10$升$13.2$摄氏度的水，方法是在第一天晚上放出$8$升水，并将剩下的水与第二和第三天流入水坝的水混合。

示例输入2

4 15
0 15
2 5
3 6
4 4

示例输出2

0.0000000
0.6666667
1.8666667
2.9333333

示例输入3

4 15
1000000000 15
9 5
8 6
7 4

示例输出3

1000000000.0000000
666666669.6666666
400000005.0000000
293333338.8666667

尽管水的温度可能超过$100$摄氏度，我们假设水不会蒸发。