Hotel

Source: POJ

Version: Phuoc Hung OJ Extended

Problem Statement

A hotel has $N$ consecutive rooms numbered $1$ through $N$, initially all empty. Process $M$ requests:

• 1 D: a group needs exactly $D$ consecutive rooms. If possible, choose the free block with the smallest starting index, print that start, and mark all $D$ rooms occupied. If no block exists, print 0.
• 2 X D: vacate rooms $X,X+1,\ldots,X+D-1$. Some of them may already be empty.

Input

The first line contains $N,M$.

The next $M$ lines contain the requests.

Output

For every type 1 request, print the selected starting room or 0.

Subtasks

• Subtask 1 — 20%: $1\le N,M\le50$.
• Subtask 2 — 30%: $1\le N,M\le5000$.
• Subtask 3 — 50%: $1\le N\le50000$, $1\le M<50000$, $1\le D\le N$, and every checkout range lies inside $[1,N]$.

Examples

Input

10 6
1 3
1 3
1 3
1 3
2 5 5
1 6

Output

1
4
7
0
5

Explanation

The sample is processed in order; every printed item/line corresponds to an operation that requires output.