Descripción

Robodrilo tiene un arreglo de enteros \(a\) de tamaño \(n\), donde originalmente \(a_i = 0\) para todo \(1 \leq i \leq n\) y se le ocurre aplicar algunas modificiaciones, sin embargo no tiene tiempo para realizarlas y te encarga dicha tarea.

Robodrilo tiene preparadas \(q\) preguntas y para cada pregunta te da un límite izquierdo \(l\) y un límite derecho \(r\) (inclusivo), esto porque quiere sumar \(1\) a todos los elementos en ese rango.

Ayuda a Robodrilo a realizar dichas modificaciones para conocer el arreglo resultante.

Entrada

Un entero \(n\) \((1 \leq n \leq 10^6)\), el tamaño del arreglo, y un entero \(q\) \((1 \leq q \leq 10^6)\), el número de preguntas.

Las siguientes \(q\) líneas contienen dos enteros \(l\) y \(r\) \((1 \leq l \leq r \leq n)\).

Salida

En una sola línea muestra \(n\) enteros \(a_1, a_2, a_3, ..., a_n\), después de haber realizado las \(q\) modificaciones.

Ejemplo

Entrada

5 3
1 2
4 4
2 2

Salida

1 2 0 1 0

Entrada

10 6
2 5
2 5
2 5
2 5
2 5
2 5

Salida

0 6 6 6 6 0 0 0 0 0