著名计算机科学家 Maksim 在网络领域提出了一种新协议，Ramazan 建议将其命名为 cerr_maksim。

为简化起见，假设网络中有两台计算机，它们通过一条吞吐量为 $w$ 的线路连接。文件从第一台计算机传输到第二台计算机。传输一个大小为 $s$ 的文件需要 $\frac{s}{w}$ 秒。

现有 $n$ 个文件需要传输，每个文件都有一个开始传输的时刻 $t_i$、大小 $s_i$ 和优先级 $p_i$。如果多个文件同时传输，线路的吞吐量将根据它们的优先级按比例分配给各个传输任务。

对于每个文件，请计算它到达第二台计算机的时刻。

输入格式

第一行包含两个整数 $n, w$ ($1 \le n \le 2 \cdot 10^5, 1 \le w \le 10^7$)，分别表示文件数量和线路吞吐量。

接下来的 $n$ 行，每行包含三个整数 $t_i, s_i, p_i$ ($1 \le t_i \le 10^7, 1 \le s_i \le 10^7, 1 \le p_i \le 100$)，分别表示传输开始时间、文件大小和优先级。

输出格式

输出 $n$ 个实数，第 $i$ 个数表示第 $i$ 个文件传输完成的时刻。

如果每个答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。

样例

输入格式 1

2 10
0 100 2
4 200 1

输出格式 1

13
30

输入格式 2

2 10
30 200 1
10 100 2

输出格式 2

50
20