Dynamic memory allocation

Kamila is designing a new programming language. She has already written a precise specification for the memory management constructs, but the implementation is still missing. Build the memory management system her specification describes.

The available memory is an array of $n$ bytes numbered $0$ through $n-1$. At the beginning every byte is free, meaning no byte is allocated. The system then processes a sequence of queries in order, allocating and freeing bytes.

An allocation query is given by one integer $\ell$. The system finds a block of $\ell$ consecutive free bytes, allocates them, and returns the position of the first byte of that block. If several such blocks exist, the one starting at the smallest position is chosen. If no such block exists, the query is rejected and the system returns $-1$. A rejected query leaves the memory unchanged.

A freeing query is given by two integers $x$ and $\ell$. The system marks the $\ell$ consecutive bytes starting at position $x$ as free and returns the number of bytes it actually freed. A byte counts as actually freed when it was not free immediately before the query.

The first line contains the number of bytes in the memory $n$ and the number of queries $q$ ($1 \le n, q \le 3 \times 10^5$).

Each of the next $q$ lines describes one query. The first integer on a line is the query type, where $1$ means allocation and $2$ means freeing. An allocation query continues with one integer $\ell$ ($1 \le \ell \le n$). A freeing query continues with two integers $x$ and $\ell$ ($0 \le x \le n-1$, $1 \le \ell \le n-x$).

For every query, print the value returned by the system on its own line, in the given order.