Problema B - Agua en Polvo 2

Felipe y su tripulación continuaron avanzando por los pasillos de MANDRÁGORA-88b hasta llegar a un ala del laboratorio que, sorprendentemente, permanecía intacta.

Mientras el resto de la estación estaba sumida en el caos, ahí todo parecía funcionar con normalidad. Los robots asistentes iban de un lado a otro cargando tubos de ensayo, macetas, aspersores y frascos etiquetados con símbolos incomprensibles.

En el centro del laboratorio encontraron a un científico llamado David Bowie, tan concentrado en su trabajo que no se había dado cuenta de que la estación entera estaba fuera de control.

—¡Perfecto! —exclamó David al verlos entrar—. Llegan justo a tiempo para presenciar mi mayor descubrimiento.

David les explicó que había inventado el agua en polvo: un polvo que, al mezclarlo con agua, producía todavía más agua.

Pero eso no era todo.

Había desarrollado una versión mejorada: Agua en Polvo 2.

Esta nueva fórmula funcionaba como un fertilizante imposible. Si se colocaba sobre una hilera de plantas, cada vez que una planta recibía una gota de agua, crecía exactamente 1 centímetro, sin importar su tamaño anterior.

Emma quedó fascinada. Si aquello funcionaba, podría transformar desiertos enteros en oasis y ayudar a acabar con la hambruna en el universo.

Para probar la fórmula, David preparó una hilera de n plantas en el laboratorio hidropónico. Inicialmente, todas las plantas miden 0 centímetros.

Luego se realizan t rociadas de agua. Cada rociada afecta a todas las plantas desde la posición l hasta la posición r, inclusive. Cada planta dentro de ese rango crece 1 centímetro.

Tu tarea es determinar la altura final de cada planta después de todas las rociadas.

Fig 1. Flores del Dr. David Bowie

Entrada

La primera línea contiene dos enteros n y t, el número de plantas y el número de rociadas.

Cada una de las siguientes t líneas contiene dos enteros l y r, que indican que se rociaron las plantas desde la posición l hasta la posición r.

Salida

Imprime n enteros separados por espacios: las alturas finales de las plantas después de todas las rociadas.

Límites

• 1 <= n <= 1000
• 0 <= t <= 100
• 1 <= l <= r <= n

Ejemplo 1

Entrada

5 3
1 3
2 5
4 4

Salida

1 2 2 2 1

Explicación

Inicialmente las plantas tienen altura:

0 0 0 0 0

Después de rociar de 1 a 3:

1 1 1 0 0

Después de rociar de 2 a 5:

1 2 2 1 1

Después de rociar de 4 a 4:

1 2 2 2 1

Ejemplo 2

Entrada

4 0

Salida

0 0 0 0

Ejemplo 3

Entrada

6 2
1 6
3 5

Salida

1 1 2 2 2 1

Grupos de prueba

Los casos de prueba están divididos de la siguiente manera:

Nota

Los índices de las plantas empiezan en 1.