N. Менеджер памяти

В распоряжении менеджера массив из $N$ последовательных ячеек памяти, пронумерованных от $1$ до $N$. Он обрабатывает запросы двух видов.

Выделение с параметром $K$: приложение просит $K$ последовательных свободных ячеек. Если подходящий блок есть, менеджер обязан его выделить, причём непосредственно перед первой ячейкой выделенного блока не должно оставаться свободной ячейки. Если подходящего блока нет, запрос отклоняется.

Освобождение с параметром $T$: память, выделенная по запросу номер $T$, освобождается и снова может использоваться. Если запрос $T$ был отклонён, освобождение игнорируется.

В исходной задаче не сказано, какой из подходящих свободных блоков выбирать. Здесь правило зафиксировано: наибольший свободный блок, при равных размерах — самый левый.

Первая строка содержит числа $N$ и $M$ ($1 \le N \le 2^{31} - 1$, $1 \le M \le 10^5$) — количество ячеек и количество запросов.

Каждая из следующих $M$ строк содержит либо положительное число $K$ ($1 \le K \le N$) — запрос на выделение, либо отрицательное число $-T$ ($1 \le T < i$ для $i$-го запроса) — запрос на освобождение.

Для каждого запроса на выделение выведите номер первой ячейки выделенного блока или $-1$, если запрос отклонён.