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

bq. Yellow sun, its evil twin,
In the black, the winds deliver him

_“Yellow sun, its evil twin,_
 _In the black, the winds deliver him"_

Umanitatea se află în pragul colapsului nuclear. Dr. Merkwürdigliebe proiectează un sistem de operare pentru ghidarea rachetelor. Supravieţuirea umanităţii depinde de algoritmul de alocare a memoriei, implementat de funcţia kmalloc. Această funcţie primeşte un singur parametru size, număr natural, identifică o zonă continuă liberă de memorie de mărime $2^size^$ şi returnează adresa de început a acesteia. După acest moment, zona respectivă de memorie devine ocupată. Sistemul de operare are la dispoziţie $N$ octeţi numerotaţi de la $0$ la $N-1$. Se dau $P$ intervale continue de memorie, care sunt rezervate deja şi nu pot fi folosite pentru alocare. Funcţia kmalloc va fi apelată până la întâlnirea lui $-1$.
Programul pe care îl veţi scrie pentru a salva umanitatea va furniza o implementare a funcţiei kmalloc şi nu va citi şi nu va scrie din/în niciun fişier. În schimb, programul vostru va interacţiona cu un program al comisiei care ruleazǎ în paralel.

h2. Mod de interacţiune:
 
Va trebui să citiţi de la intrarea standard, de pe prima linie, două numere întregi $N$ şi $P$ cu semnificaţiile din enunţ. Următoarele $P$ linii vor conţine câte două numere întregi între $0$ şi $N–1$, reprezentând adresa de început şi cea de sfârşit a intervalelor rezervate. Aceste intervale nu se vor suprapune şi vor fi date în ordinea crescătoare a adreselor ocupate. Valorile parametrilor corespunzători apelurilor funcţiei kmalloc vor fi citite câte unul pe linie. Programul va trebui să afişeze pe ecran adresa de memorie de început a zonei allocate, înainte de a citi valoarea parametrului care corespunde următorului apel al funcţiei kmalloc. Se garantează că toate cererile de alocare de memorie pot fi satisfăcute de către un algoritm potrivit.
 
*Atenţie* Citiţi documentaţia corespunzătoare 'problemelor interactive':documentatie/tutorial#probleme-interactive pentru a vedea ce modificări trebuie făcute în programul vostru faţă de problemele care folosesc fişiere de intrare / ieşire şi pentru a vedea cum vă puteţi testa sursele.

Mod de interacţiune: 'documentatie probleme interactive':/documentatie/tutorial#probleme-interactive.
Va trebui să citiţi de la intrarea standard, de pe prima linie, două numere întregi $N$ şi $P$ cu semnificaţiile din enunţ. Următoarele $P$ linii vor conţine câte două numere întregi între $0$ şi $N–1$, reprezentând adresa de început şi cea de sfârşit a intervalelor rezervate. Aceste intervale nu se vor
suprapune şi vor fi date în ordinea crescătoare a adreselor ocupate. Valorile parametrilor corespunzători apelurilor funcţiei kmalloc vor fi citite câte unul pe linie. Programul va trebui să afişeze pe ecran adresa de memorie de început a zonei allocate, înainte de a citi valoarea parametrului care corespunde următorului apel al funcţiei kmalloc. Se garantează că toate cererile de alocare de memorie pot fi satisfăcute de către un algoritm potrivit.
Recomandări de programare
• Programatorilor în $C$ li se recomandă să apeleze $"fflush(stdout);"$ după ce au terminat de scris o linie completă la ieşire.
• Programatorilor în $C++$ care folosesc streamuri li se recomandă $"cout.flush();"$ după ce au terminat de scris o linie completă la ieşire.
• Programatorilor în $Pascal$ li se recomandă să apeleze $"flush(output);"$ după ce au terminat de scris o linie completă la ieşire.
Recomandăm ca programatorii $C/C++$ care citesc datele cu funcţia $scanf()$, să nu specifice marcajul de sfârşit de linie $'\n'$ în şirul care descrie formatul de citire. De exemplu, citirea valorilor variabilelor $N$ şi $P$ se va realiza astfel: $scanf("%lld %d", &N, &P)$;

h2. Restricţii

* $1 ≤ N ≤ 2^62^$

 
* $1 ≤ N ≤ 262$

* Numărul de query-uri nu va depăşi $600 000$
* $0 ≤ P ≤ 100 000$
* Programul comisiei se va adapta la strategia aleasă de concurent.
* În cazul în care programul vostru nu poate răspunde la o secvenţă validă de alocări, se vor acorda punctaje parţiale în funcţie de poziţia primului răspuns nepotrivit.

h2. Exemplu

table(example). |_. Citire |_. Afişare |_. Explicaţii |
| 13 2 |   | $13$ octeţi disponibili numerotaţi de la $0$ la $12$, $2$ intervale rezervate |
| 5 5 |   | Octetul 5 este rezervat |
| 6 6 |   | Octetul 6 este rezervat |
| 2 |   | Se doreşte alocarea unei zone de 4 octeţi |
|   | $0$ | Alocă octeţii 0, 1, 2, 3 |
| $0$ | 0 | Se doreşte alocarea unei zone de 1 octet |
|   | 4 | Alocă octetul 4 |
| 1 |   | Se doreşte alocarea unei zone de 2 octeţi |
|   | 7 | Alocă octeţii 7, 8 |
| 2 |   | Se doreşte alocarea unei zone de 4 octeţi |
|   | 9 | Alocă octeţii 9, 10, 11, 12 |
| -1 |   | Final de program |

table(example). |_. kmalloc.in |_. kmalloc.out |
|13 2
5 5
6 6
2
0
1
2
-1
|0
4
7
9
|
 
 
h3. Explicaţie
 
DE EXPLICAT AICI!!!!

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

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