Пете поручили написать менеджер памяти для новой стандартной библиотеки языка H++. В распоряжении у менеджера находится массив из
N последовательных ячеек памяти, пронумерованных от
1 до
N. Задача менеджера — обрабатывать запросы приложений на выделение и освобождение памяти.
Запрос на выделение памяти имеет один параметр
K. Такой запрос означает, что приложение просит выделить ему
K последовательных ячеек памяти. Если в распоряжении менеджера есть хотя бы один свободный блок из
K последовательных ячеек, то он обязан в ответ на запрос выделить такой блок. При этом непосредственно перед самой первой ячейкой памяти выделяемого блока не должно располагаться свободной ячейки памяти. После этого выделенные ячейки становятся занятыми и не могут быть использованы для выделения памяти, пока не будут освобождены. Если блока из K последовательных свободных ячеек нет, то запрос отклоняется.
Запрос на освобождение памяти имеет один параметр
T. Такой запрос означает, что менеджер должен освободить память, выделенную ранее при обработке запроса с порядковым номером
T. Запросы нумеруются, начиная с единицы. Гарантируется, что запрос с номером
T — запрос на выделение, причем к нему еще не применялось освобождение памяти. Освобожденные ячейки могут снова быть использованы для выделения памяти. Если запрос с номером
T был отклонен, то текущий запрос на освобождение памяти игнорируется.
Требуется написать менеджер памяти, удовлетворяющий приведенным критериям.
Формат входных данных
В первой строке входных данных задаются числа
N и
M — количество ячеек памяти и количество запросов, соответственно (1 ≤
N ≤ 2
31 – 1; 1 ≤
M ≤ 10
5). Каждая из следующих
M строк содержит по одному числу: (
i+1)-я строка входных данных (1 ≤
i ≤
M) содержит либо положительное число
K, если
i-й запрос — запрос на выделение с параметром
K (1 ≤
K ≤
N), либо отрицательное число –
T, если
i-й запрос — запрос на освобождение с параметром
T (1 ≤
T <
i).
Формат выходных данных
Для каждого запроса на выделение памяти выведите результат обработки этого запроса: для успешных запросов выведите номер первой ячейки памяти в выделенном блоке, для отклоненных запросов выведите число
-1. Результаты нужно выводить в порядке следования запросов во входных данных.