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 al K-lea numar de ordine. 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, K 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, M si K, cu semnificatiile din enunt. 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, pe linii separate, al i-lea dintre ele reprezentand muncitorul care realizeaza verificarea cu numarul de ordine i, considerand muncile in ordinea in care se executa(ordonat dupa timpul de incepere al verificarii).

Restricţii

• 1 ≤ N ≤ 100.000
• 1 ≤ M ≤ 100.000
• 1 ≤ K ≤ N
• 1 ≤ A_i, B_i ≤ 1.000.000
• Se garanteaza ca pentru fiecare dintre cele M verificari vor exista cel putin K muncitori disponibil.
• Pentru 20% din teste N, M ≤ 1.000
• Pentru alte 20% din teste K = 1.
• Nu exista doua verificari care sa inceapa la acelasi moment de timp.

Exemplu

Cum se trimit solutii?