Задача G. Менеджер памяти ≡

Условие

Оперативная память компьютера может быть представлена в виде массива байт, где адрес каждого байта определяется его позицией относительно начала такого массива. В процессе своей работы различные программы могут запрашивать отдельные участки (блоки) памяти, которые должны выделяться и освобождаться по мере необходимости.

Требуется написать менеджер памяти, который хранит информацию о всех доступных блоках и отвечает за обработку запросов следующего вида.

Запрос на выделение памяти

Вначале выбирается свободный блок наименьшего размера, который может уместить запрашиваемый объем данных. Если таких блоков несколько, среди них выбирается блок с наименьшим адресом (смещением). При этом размещаемые в нем данные выравниваются по левому (нижнему) краю. В этом случае адрес свободного пространства сдвигается вверх (в сторону окончания блока).

В качестве ответа в выходной поток следует вывести адрес выделенного блока. В случае отказа от выделения памяти (если блок подходящего размера не был найден), в выходной поток выводится ' − 1'.

Запрос на удаление

Вначале выполняется поиск выделенного блока с заданным адресом.

Если такой блок был найден, он удаляется из таблицы (дополняя окружающее его свободное пространство), а в выходной поток выводится его размер. В противном случае, выводится ' − 2'.

Формат входного файла

В начале входного файла "input.txt" хранятся два натуральных числа: L — доступный объем памяти и n — общее число запросов. Далее следует ровно n строк, записанных в следующем формате:

new <размер_блока> — запрос на выделение;

del <адрес_блока> — запрос на удаление.

Формат выходного файла

Выходной файл "output.txt" должен содержать результаты выполнения каждого такого запроса.

Ограничения

Полагается, что адресация памяти начинается с нуля.

0 < L ≤ 10⁹, 0 < n ≤ 10⁵

Примеры тестов

1024
10
new 100
new 10
new 100
new 10
new 100
del 210
del 100
new 5
del 110
new 110

0
100
110
210
220
10
10
100
100
105

1024
10
new 1000
new 1000
del 0
new 128
del 45
new 256
new 360
del 128
del 128
new 200

0
-1
1000
0
-2
128
384
256
-2
128