Avem un calculator cu $N$ procesoare. Există $M$ taskuri care trebuie executate, fiecare având un timp de început $S{~i~}$ şi o durată de procesare $D{~i~}$. Taskurile trebuie executate în ordine cronologică şi fiecare task trebuie executat pe procesorul cu indicele cel mai mic disponibil la momentul de timp $S{~i~}$.

h2. Cerintă

h2. Cerinţă

Trebuie calculat pentru fiecare task procesorul care îl va executa.

* $1 ≤ N ≤ 1.000.000$
* $1 ≤ M ≤ 100.000$

* Se garantează ca fiecare task poate fi executat
* Toate valorile $S{~i~}$ sunt distincte

* Pentru orice $i$ între $1$ şi $M$, {$1 ≤ S{~i~} ≤ 2*10^9^$} şi {$1 ≤ S{~i~}+D{~i~} ≤ 2*10^9^$}
* Pentru orice $i$ între $1$ şi $M-1$, {$S{~i~} < S{~i+1~}$}
* Se garantează că fiecare task poate fi executat

* Procesorul care execută taskul $i$ este ocupat la momentele de timp $[S{~i~}, S{~i~} + D{~i~})$
h2. Exemplu

5445