==Include(page="template/taskheader" task_id="hotel")==

==Include(page="template/raw")==
 

Hotelul "Informatica" este unul dintre cele mai luxoase hoteluri din Galaciuc. De-a lungul anului multe grupuri de turisti sosesc la acest hotel sau il parasesc la sfarsitul sejurului, asa ca situatia exacta a camerelor libere si ocupate este destul de greu de aflat, mai ales ca hotelul are un numar mare de camere. Dar anul acesta proprietarul hotelului s-a decis ca are nevoie de o schimbare. De aceea v-a angajat pe dumneavoastra pentru a scrie un program eficient, care sa raspunda necesitatilor sale.

h2. Date de intrare

Pe prima linie a fisierului $hotel.in$ se vor afla numerele $N$ si $P$, reprezentand numarul de camere ale hotelului (numerotate de la $1$ la {$N$}), respectiv numarul de instructiuni care urmeaza. Pe fiecare din urmatoarele $P$ linii se va afla un numar $c$, reprezentand tipul instructiunii ce va fi descrisa pe linia respectiva:

Pe prima linie a fisierului $hotel.in$ se vor afla numerele $N$ si $P$, reprezentand numarul de camere ale hotelului (numerotate de la $1$ la {$N$}), respectiv numarul de instructiuni care urmeaza.
Pe fiecare din urmatoarele $P$ linii se va afla un numar $c$, reprezentand tipul instructiunii ce va fi descrisa pe linia respectiva:

* daca $c$ are valoarea $1$, atunci el va fi urmat (pe aceeasi linie) de alte $2$ numere, $i$ si $M$, reprezentand numarul primei camere distribuite grupului abia sosit si numarul de membri ai grupului
* daca $c$ are valoarea $2$, atunci el va fi urmat (pe aceeasi linie) de alte $2$ numere, $i$ si $M$, reprezentand numarul primei camere care va fi eliberata de grupul care tocmai pleaca, precum si numarul de membri ai grupului care paraseste hotelul

h2. Restrictii si precizari

* $3 ≤ N ≤ 100.000$
* $3 ≤ P ≤ 200.000$
* In orice camera poate fi cazat la un moment dat un singur turist.

S 3 <= N <= 100.000
 
S 3 <= P <= 200.000
 
S In orice camera poate fi cazat la un moment dat un singur turist.

h2. Exemplu

table(example). |_. hotel.in |_. hotel.out |
| 12 10
3
1 2 3
1 9 4
3

hotel.in hotel.out
 
12 10 12
 
3 4
 
1 2 3 4
 
1 9 4 6
 
3 10
 

2 2 1

3

2 9 2

3

2 3 2

3
| 12
4
4
6
10 |

3

==Include(page="template/taskfooter" task_id="hotel")==

462