#21 Memory Allocator

製作者:QCFium

難易度
8

## 問題 あなたは$N$バイトのメモリを持っています。 先頭を0バイト目とし、最後を$N-1$バイト目とします。 以下のクエリを$Q$個処理してください。 - $i(1 \le i \le Q)$個目のクエリでは整数$A_i$及び$B_i$が与えられる。 $A_i$はクエリの種類を表し、1又は2である。 - $A_i=1$の場合 メモリのなかで今確保されていない領域から最もメモリの先頭に近い連続する$B_i$バイトの領域を確保し、確保した領域の先頭がメモリ上で何バイト目かを出力する。確保された領域は後述する解放クエリによって解放されない限り再び確保に使用することはできない。 但しそのような場所が存在しない場合は何も確保せず```-1```を出力する。 - $A_i =2$の場合 $B_i$個目のクエリで確保された領域を解放する。従ってその領域は再び確保に利用できる。 但しそのクエリにおける確保が失敗していたならば何もしない。 ## 入力 $N \hspace{7pt} Q$ $A_1 \hspace{7pt} B_1$ $A_2 \hspace{7pt} B_2$ $A_3 \hspace{7pt} B_3$ $ \hspace{13pt} \vdots$ $A_Q \hspace{7pt} B_Q$ ## 制約 $1 \le N \le 10^9$ $1 \le Q \le 5 \times 10^ 5$ 以下$1 \le i\le Q$とする : $A_i = 1,2$ $A_i=1$のとき$1 \le B_i \le 10^9$ $A_i = 2$のとき$1 \le B_i \lt i$ - 解放の対象となるクエリは確保クエリである : $A_i = 2$のとき$A_{B_i}=1$ - 二重解放はされない : $1 \le j \le Q$、$i \neq j$かつ$A_i=B_i=2$のとき$B_i \neq B_j$ ## 出力, その他注意 各確保クエリに対して、指定された値を出力し、改行せよ。 これはインタラクティブ問題ではないので出力の度にflushする必要はなく、クエリに対して(次のクエリを入力する前に)直ちに答えを出力する必要もない。 入出力量が多いのでiostream系の入出力機能を使うとTLEする可能性がある。 ## 例 ### 入力例1 ``` 9 6 1 2 1 4 1 3 2 2 1 5 1 3 ``` ### 出力例1 ``` 0 2 6 -1 2 ``` ### 入力例2 ``` 9 7 1 3 1 3 1 3 2 1 2 3 2 2 1 9 ``` ### 出力例2 ``` 0 3 6 0 ```
提出