ネットワーク分野で著名な計算機科学者であるMaksimは、Ramazanが cerr_maksim と呼ぶことを提案した新しいプロトコルを考案しました。

単純化のため、ネットワーク上には2台のコンピュータがあり、それらはスループット $w$ の回線で接続されているとします。ファイルは最初のコンピュータから2番目のコンピュータへ転送されます。サイズ $s$ のファイルの転送には $\frac{s}{w}$ 秒かかります。

転送すべきファイルが $n$ 個あり、各ファイルには転送開始時刻 $t_i$、サイズ $s_i$、優先度 $p_i$ が設定されています。複数のファイルが同時に転送されている場合、回線のスループットは各ファイルの優先度に比例して分割されます。

各ファイルについて、2番目のコンピュータに到達する時刻を計算してください。

入力

1行目には、2つの整数 $n, w$ ($1 \le n \le 2 \cdot 10^5, 1 \le w \le 10^7$) が与えられます。これはファイルの数と回線のスループットを表します。

続く $n$ 行の各行には、3つの整数 $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