Maksim, znany informatyk zajmujący się sieciami komputerowymi, opracował nowy protokół, który Ramazan zaproponował nazwać cerr_maksim.

Dla uproszczenia przyjmijmy, że w sieci znajdują się dwa komputery połączone przewodem o przepustowości $w$. Pliki są przesyłane z pierwszego komputera do drugiego. Przesłanie pliku o rozmiarze $s$ zajmuje $\frac{s}{w}$ sekund.

Do przesłania jest $n$ plików, z których każdy ma moment $t_i$, w którym rozpoczyna się jego przesyłanie, rozmiar $s_i$ oraz priorytet $p_i$. Jeśli wiele plików jest przesyłanych jednocześnie, przepustowość przewodu jest dzielona między transfery proporcjonalnie do ich priorytetów.

Dla każdego pliku oblicz moment, w którym dotrze on do drugiego komputera.

Wejście

Pierwsza linia zawiera dwie liczby całkowite $n, w$ ($1 \le n \le 2 \cdot 10^5$, $1 \le w \le 10^7$) — liczbę plików oraz przepustowość przewodu.

Każda z kolejnych $n$ linii zawiera trzy liczby całkowite $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$) — czas rozpoczęcia transferu, rozmiar i priorytet.

Wyjście

Wypisz $n$ liczb rzeczywistych, gdzie $i$-ta liczba to moment zakończenia transferu $i$-tego pliku.

Twoje odpowiedzi zostaną uznane za poprawne, jeśli dla każdej z nich błąd bezwzględny lub względny nie przekracza $10^{-6}$.

Przykład

Wejście 1

2 10
0 100 2
4 200 1

Wyjście 1

13
30

Wejście 2

2 10
30 200 1
10 100 2

Wyjście 2

50
20