Fişierul intrare/ieşire:	muncitori.in, muncitori.out	Sursă	Algoritmiada 2012, Runda 4
Autor	Adrian Diaconu	Adăugată de	Cezar Mocan •CezarMocan
Timp execuţie pe test	0.15 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Muncitori

Cei N muncitori de la Fabrica de Bere au o zi grea astazi, din cauza ca trebuie sa verifice calitatea celor M loturi propuse pentru export. Directorul Fabricii a afisat o lista cu momentele in care ar trebui sa inceapa verificarea fiecarui lot, A_i, cat si durata aproximativa pe care un muncitor o petrece facand respectiva verificare, B_i. Pentru a putea pleca acasa cat mai devreme posibil, muncitorii vor sa faca aceste verificari intr-un mod foarte organizat: vor lua loturile in ordine cronologica dupa momentul de start scris pe lista, fiecarui lot fiindu-i atribuit muncitorul liber care are numarul de ordine minim. Odata ce un muncitor incepe verificarea lotului i, el va fi ocupat pentru B_i secunde, fiind liber din nou la momentul A_i + B_i.

Cerinta

Dandu-se N, M si cele M perechi A B, sa se determine si sa se afiseze pentru fiecare lot ce muncitor ii va fi asociat.

Date de intrare

Fişierul de intrare muncitori.in va contine pe prima linie numerele N si M, reprezentand numarul de muncitori si respectiv de loturi care trebuie verificate. Urmatoarele M linii vor contine cate o pereche A_i B_i, momentul de start si durata pentru verificarea lotului i.

Date de ieşire

În fişierul de ieşire muncitori.out se vor afisa M numere naturale, al i-lea dintre ele reprezentand muncitorul care realizeaza verificarea cu numarul de ordine i.

Restricţii

• 1 ≤ N ≤ 100.000
• 1 ≤ M ≤ 100.000
• 1 ≤ A_i, B_i ≤ 1.000.000.000
• Se garanteaza ca pentru fiecare dintre cele M verificari va exista cel putin un muncitor disponibil.
• Nu exista doua verificari care sa inceapa la acelasi moment de timp.

Exemplu

Explicaţie

...

Cum se trimit solutii?