Hay ~n~ segmentos de recta cuyos extremos tienen coordenadas enteras. La coordenada ~x~ izquierda de cada segmento es ~0~ y la coordenada ~x~ derecha es ~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.

Entrada

La primera recta tiene dos enteros ~n~ y ~m~: el número de segmentos de recta y la coordenada ~x~ máxima. Las siguientes ~n~ rectas describen los segmentos de recta. Cada recta tiene dos enteros ~y_1~ e ~y_2~: hay un segmento de recta entre los puntos ~(0,y_1)~ y ~(m,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 y_1,y_2 \leq 10^9~

Ejemplo de Entrada

4 5
1 6
7 2
5 5
10 0

Ejemplo de Salida

10 8 6 5 5 6