Problem G
Memory Device

Grandpa has a special memory device. The device’s memory is an array of length $n$, numbered from $0$ to $n-1$. The device also support $2$ operations: Allocation and Deallocation.

For an allocation operation, an integer $l$ will be given. The device will have to find the left-most contiguous segment of free memory with a length of at least $l$. Denote the start of this segment to be cell $p$. The device will then mark all cells from $p$ to $p+l-1$ as used and prints $p$. If no segment can be found, the device will just print $-1$.

For a deallocation operation, two integers $x$ and $l$ will be given. The device will mark all cells from $x$ to $x+l-1$ as free. Then the device will print $k$, the number of cells that were actually freed (i.e. non-free prior to the operation).

Alas, the output screen broke so the device is unable to show the results of each operation! Thus, Grandpa have asked you, his genius programming grandkid, to fix the device. You are to restore the result printing functionality!

As you tinkered about, you realize you don’t have access to its internal algorithm or its current state whatsoever, but you are determined fix printing functionality regardless (even if you have to reinvent the memory’s allocation and deallocation algorithm from scratch!).

To prove that it is working, you start with a device that is initially filled with empty cells and will do $q$ operations. You are to output $q$ numbers, the result after each operation. Fix it and make Grandpa proud!

Input

The first line contains $2$ integers $n$ and $q$ ($ 1 \leq n,q \leq 300\, 000$) The next $q$ lines, each will contain one of the two query types:

• $1$ $l$ — Allocate a segment memory of length $l$ ($1 \leq l \leq n-1$).

• $2$ $x$ $l$ — Deallocate cells from $x$ to $x+l-1$ ($0 \leq x \leq x+l-1 \leq n-1$).

Output

For each query, print a single integer on a new line.

10 6
1 9
1 1
1 5
2 3 6
1 5
2 8 1

0
9
-1
6
3
0