B. Менеджер памяти
ограничение по времени на тест
1 second
ограничение по памяти на тест
64 megabytes
ввод
stdin
вывод
stdout

До релиза первой национальной операционной системы BerlOS осталось совсем чуть-чуть. В ней не готовы всего несколько компонентов — менеджер памяти в том числе. По задумке разработчиков, в первой версии он будет очень прост и прямолинеен. Менеджер памяти будет поддерживать три операции:

  • alloc n — выделить n байт памяти и вернуть идентификатор выделенного блока x;
  • erase x — удалить блок с идентификатором x;
  • defragment — дефрагментировать свободную память, переместив все блоки максимально к началу памяти, сохранив их относительный порядок.

Модель памяти в данном случае очень проста. Память представляет собой последовательность m байт, условно пронумерованных от первого до m-го.

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

Вторая операция erase x принимает в качестве параметра идентификатор некоторого блока. Она возвращает память системе, помечая байты этого блока свободными для последующего использования. В том случае, если этому идентификатору не соответствует ранее выделенный блок, который еще не был удален, то функция возвращает специальное значение ILLEGAL_ERASE_ARGUMENT.

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

В текущей реализации требуется использовать в качестве идентификаторов последовательные целые числа от 1. Каждый успешный вызов alloc должен возвращать очередное число. Неудачные вызовы alloc не оказывают влияния на описанную нумерацию.

Ваша задача состоит в том, чтобы написать реализацию менеджера памяти. Для каждой команды alloc нужно выводить возвращаемое значение. Также следует выводить ILLEGAL_ERASE_ARGUMENT для всех неудачных вызовов erase.

Входные данные

В первой строке входных данных содержатся два целых положительных числа t и m (1 ≤ t ≤ 100;1 ≤ m ≤ 100), где t — количество операций, заданных менеджеру памяти на исполнение, а m — размер доступной памяти в байтах. Далее в t строках заданы сами операции. Первая операция задается строкой alloc n (1 ≤ n ≤ 100), где n целое число. Вторая задается строкой erase x, где x произвольное 32-битное целое знаковое число. Третья операция задается строкой defragment.

Выходные данные

Выведите последовательность строк. Каждая строка должна содержать либо результат работы операции alloc, либо ILLEGAL_ERASE_ARGUMENT как результат неудачного выполнения операции erase. Вывод следует осуществлять в порядке совершения операций. Реализация alloc должна возвращать в качестве идентификаторов выделенных блоков целые числа, начиная с 1.

Примеры
Входные данные
6 10
alloc 5
alloc 3
erase 1
alloc 6
defragment
alloc 6
Выходные данные
1
2
NULL
3