Maksim, un informaticien renommé dans le domaine des réseaux, a imaginé un nouveau protocole que Ramazan a suggéré d'appeler cerr_maksim.

Pour simplifier, supposons qu'il y ait deux ordinateurs dans le réseau, reliés par un câble d'un débit $w$. Des fichiers sont transférés du premier ordinateur vers le second. Le transfert d'un fichier de taille $s$ prend $\frac{s}{w}$ secondes.

Il y a $n$ fichiers à transférer, chacun ayant un instant $t_i$ où il commence à être transféré, une taille $s_i$ et une priorité $p_i$. Si plusieurs fichiers sont transférés simultanément, le débit du câble est divisé entre les transferts proportionnellement à leurs priorités.

Pour chaque fichier, calculez l'instant où il atteindra le second ordinateur.

Entrée

La première ligne contient deux entiers $n, w$ ($1 \le n \le 2 \cdot 10^5$, $1 \le w \le 10^7$) — le nombre de fichiers et le débit du câble.

Chacune des $n$ lignes suivantes contient trois entiers $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$) — l'instant de début du transfert, la taille et la priorité.

Sortie

Affichez $n$ nombres réels, le $i$-ième nombre étant l'instant où le transfert du $i$-ième fichier est terminé.

Vos réponses seront considérées comme correctes si, pour chacune d'elles, son erreur absolue ou relative n'excède pas $10^{-6}$.

Exemples

Entrée 1

2 10
0 100 2
4 200 1

Sortie 1

13
30

Entrée 2

2 10
30 200 1
10 100 2

Sortie 2

50
20