Hotel

A hotel has $N$ rooms ($1 \le N \le 50{,}000$) arranged in a single row along a hallway, numbered $1$ through $N$. Initially every room is empty.

You must process $M$ check-in and check-out requests ($1 \le M < 50{,}000$) in order.

• Check-in 1 D ($1 \le D \le N$): assign a block of $D$ consecutive rooms. Among all starting positions $r$ where rooms $r, r+1, \dots, r+D-1$ are all currently empty, choose the smallest $r$, mark those rooms as occupied, and output $r$. If no block of $D$ consecutive empty rooms exists, assign nothing and output $0$.
• Check-out 2 X D ($1 \le X \le N-D+1$): mark rooms $X, X+1, \dots, X+D-1$ as empty. Some or all of these rooms may already be empty; that is allowed and has no additional effect.

• Line 1: two integers $N$ and $M$.
• The next $M$ lines: each line is a request in one of two forms.
  • 1 D — a check-in request for $D$ rooms.
  • 2 X D — a check-out request for rooms $X$ through $X+D-1$.

• For each check-in request, print on its own line the number $r$ of the first room in the assigned block, or $0$ if the request cannot be satisfied. Check-out requests produce no output.