Maksim, un conocido científico informático en el campo de las redes, ideó un nuevo protocolo que Ramazan sugirió llamar cerr_maksim.

Para simplificar, supongamos que hay dos computadoras en la red, conectadas por un cable con un ancho de banda $w$. Los archivos se transfieren de la primera computadora a la segunda. Transferir un archivo de tamaño $s$ toma $\frac{s}{w}$ segundos.

Hay $n$ archivos por transferir, cada uno tiene un momento $t_i$ en el que comienza a transferirse, un tamaño $s_i$ y una prioridad $p_i$. Si se transfieren varios archivos simultáneamente, el ancho de banda del cable se divide entre las transferencias proporcionalmente a sus prioridades.

Para cada archivo, calcule el momento en el que llegará a la segunda computadora.

Entrada

La primera línea contiene dos enteros $n, w$ ($1 \le n \le 2 \cdot 10^5$, $1 \le w \le 10^7$) — el número de archivos y el ancho de banda del cable.

Cada una de las siguientes $n$ líneas contiene tres enteros $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$) — el tiempo de inicio de la transferencia, el tamaño y la prioridad.

Salida

Imprima $n$ números reales, donde el $i$-ésimo número sea el momento en el que se completa la transferencia del $i$-ésimo archivo.

Sus respuestas se considerarán correctas si, para cada una de ellas, su error absoluto o relativo no excede $10^{-6}$.

Ejemplos

Entrada 1

2 10
0 100 2
4 200 1

Salida 1

13
30

Entrada 2

2 10
30 200 1
10 100 2

Salida 2

50
20