8. Abnormálne Veľký Hotel

Úloha

Prideľovač¹ pracuje v hoteli s \(n\) izbami číslovanými od \(0\) po \(n - 1\) vrátane.

Prideľovač dostáva dva druhy požiadaviek:

• check-in požiadavky, ktoré obsahujú číslo \(x\) – počet miestností potrebný pre skupinu hostí. Prideľovač týchto hostí ubytuje do \(x\) po sebe idúcich voľných izieb. Prideľovač vždy vyberie taký usek izieb, ktorý minimalizuje minimálne číslo izby zo všetkých čísel izieb v úseku.
• check-out požiadavky, ktoré obsahujú číslo \(i\) – index skoršej check-in požiadavky. Check-in požiadavky indexujeme od \(0\) a do indexovania nerátame check-out požiadavky. Skupina hostí ubytovaná v \(i\)-tej check-in požiadavke uvoľní svoje miestnosti a opustí hotel.

Je zaručené, že Prideľovač bude schopný naplniť všetky požiadavky.

Vašou úlohou je vypísať pre každú check-in požiadavku číslo najmenšej izby z úseku miestností pridelených skupine hostí.

Formát vstupu

Na prvom riadku vstupu sú dve medzerou oddelené prirodzené čísla \(n\), \(q\) – počet izieb v hoteli a počet požiadaviek.

Nasleduje \(q\) riadkov. Každý riadok obsahuje jednu požiadavku. Check-in požiadavky majú tvar I x, \(x\) – počet miestností potrebný pre skupinu hostí. Check-out požiadavky majú tvar O i, \(i\) – index skoršej check-in požiadavky.

Formát výstupu

Pre každú check-in požiadavku vypíšte na jeden riadok jediné číslo – číslo najmenšej izby z úseku miestností pridelených skupine hostí.

Hodnotenie

Sú 4 sady vstupov po 2 bodoch. Platia v nich nasledovné obmedzenia:

Príklad

Input:

9 7
I 3
I 3
O 0
I 2
I 2
I 1
I 1

Output:

0
3
0
6
2
8

Reprezentujme hotel stringov znakov, kde i-ty znak reprezentuje stav i-tej izby. Spočiatku je hotel prázdny ---------. Príde skupina troch hostí 000------. Príde ďaľšia skupina troch hostí 000111---. Odubytuje sa skupina hostí 0 ---111---. Príde skupina 2 hostí 22-111--- a na to ďaľšia 22-11133-. Nakoniec príde jeden človek 22411133- a za ním ďalší 224111335.