Descripción

Después de varias visitas, Maullin quiere saber qué opinan los animalitos sobre los lugares turísticos que le recomendaron visitar.
Los animalitos le van a dar rangos \([L, R]\), donde en ese rango significa que sí les gustó, así que hay que ir acumulando un voto en todo el rango.

Al final, Maullin quiere saber cuáles son los lugares más preferidos por todos, así que les preguntará a los animalitos los rangos que les gustaron.

Inicialmente, Maullin tiene un arreglo vacío de tamaño \(N\), cada \(i\) representa un lugar diferente.
Si \(N = 10\), el arreglo inicialmente se vería así:

\([0, 0, 0, 0, 0, 0, 0, 0, 0, 0]\).

Un animalito dice que le gustó visitar el rango \([1, 3]\), por lo que Maullin tiene que actualizar el arreglo aumentando \(1\) a todas las casillas en ese rango.

Después de la actualización, el arreglo queda así:

\([1, 1, 1, 0, 0, 0, 0, 0, 0, 0]\).

Luego, el siguiente animalito te da el rango \([2, 6]\).

Después de la actualización, el arreglo queda así:

\([1, 2, 2, 1, 1, 1, 0, 0, 0, 0]\).

El último animalito te da el rango \([8, 10]\).

Después de la actualización, el arreglo finalmente queda así:

\([1, 2, 2, 1, 1, 1, 0, 1, 1, 1]\).

Entrada

En la primera línea, dos enteros \(N\) y \(Q\) \((1 \leq N, Q \leq 10^6)\).

En las siguientes \(Q\) líneas, dos enteros \(L\) y \(R\) \((1 \leq L \leq R \leq N)\), los valores que delimitan el rango \([L, R]\).

Salida

Imprimir el arreglo final obtenido después de realizar las \(Q\) actualizaciones.

Ejemplos

Entrada

10 3
1 3
2 6
8 10

Salida

1 2 2 1 1 1 0 1 1 1

Entrada

5 1
1 5

Salida

1 1 1 1 1

Entrada

3 3
1 1
1 2
1 3

Salida

3 2 1