Hay ~n~ segmentos de recta cuyos extremos tienen coordenadas enteras. Cada coordenada ~x~ está entre ~0~ y ~m~. La pendiente de cada segmento es un entero. Para cada coordenada ~x~ ~0,1,\dots,m~, encuentre el punto máximo en cualquier segmento de recta. Si no hay segmento en algún punto, el máximo es ~-1~.

Entrada

La primera línea tiene dos enteros ~n~ y ~m~: el número de segmentos de recta y la coordenada ~x~ máxima. Las siguientes ~n~ líneas describen los segmentos de recta. Cada línea tiene cuatro enteros ~x_1, y_1, x_2~ e ~y_2~: hay un segmento de recta entre los puntos ~(x_1,y_1)~ y ~(x_2,y_2)~.

Salida

Imprima ~m+1~ enteros: los puntos máximos para ~x = 0,1,\dots,m~.

Restricciones

• ~1 \leq n, m \leq 10^5~
• ~0 \leq x_1 < x_2 \leq m~
• ~0 \leq y_1,y_2 \leq 10^9~

Ejemplo de Entrada

4 5
1 1 3 3
1 2 4 2
2 4 5 7
2 8 5 2

Ejemplo de Salida

-1 2 8 6 6 7