知名電腦科學家 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