Ú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.