== include(page="template/taskheader" task_id="proc2") ==

Poveste şi cerinţă...

Avem un calculator cu $N$ procesoare. Există $M$ taskuri care trebuie executate, fiecare având un timp de inceput $S{~i~}$ şi o durata de procesare $D{~i~}$. Taskurile trebuie executate în ordine cronologică şi fiecare task trebuie executat de procesorul cu indicele cel mai mic disponibil la momentul de timp $S{~i~}$.
 
h2. Cerintă
 
Trebuie calculat pentru fiecare task procesorul care îl va executa.

h2. Date de intrare

Fişierul de intrare $proc2.in$ ...

Fişierul de intrare $proc2.in$ conţine pe prima linie valorile $N$ şi $M$. Pe următoarele $M$ linii se vor găsi cate două numere $S{~i~}$, $D{~i~}$ separate prin spaţii, cu semnificaţia din enunţ.

h2. Date de ieşire

În fişierul de ieşire $proc2.out$ ...

În fişierul de ieşire $proc2.out$ trebuie afişate $M$ linii, pe linia $i$ se va scrie indicele procesorului care se ocupă de taskul $i$.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 1.000.000$
* $1 ≤ M ≤ 100.000$
* se garantează ca fiecare task poate fi executat
* toate valorile $S{~i~}$ sunt distincte
* procesorul care executa taskul $i$ este ocupat la momentele de timp $[S{~i~}, S{~i~} + D{~i~}]$

h2. Exemplu
table(example). |_. proc2.in |_. proc2.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 3 3
1 2
2 5
3 4
| 1
2
1

|
h3. Explicaţie

...

* La momentul de timp $1$ sunt disponibile procesoarele $1, 2, 3$. Deci taskul $1$ va fi executat de procesorul $1$.
* La momentul de timp $2$ sunt disponibile procesoarele $2, 3$. Deci taskul $2$ va fi executat de procesorul $2$.
* La momentul de timp $3$ sunt disponibile procesoarele $1, 3$. Deci taskul $3$ va fi executat de procesorul $1$.

== include(page="template/taskfooter" task_id="proc2") ==