Задачи
Менеджер памяти
Менеджер памяти
Вы работаете над созданием компилятора своего собственного языка программирования, и уже реализовали все кроме менеджера памяти (мп). мп отвечает за выделение памяти под объекты и их освобождение по ненадобности. Всего в Вашем компьютере имеется \textbf{n} последовательно расположенных байт памяти. Каждый объект требует определенное количество последовательных байт в памяти. Во время выполнения программа может присылать два типа запроса мп:
1) Выделить память под объект размером \textbf{a} байт. Эта величина может быть разной для разных объектов. Два объекта не могут иметь общей памяти.
2) Удалить заданный объект, под который раньше была выделена память.
Вам наперед известны все \textbf{m} запросов, которые будут посланы мп. Найдите вариант их обслуживания, или сообщите что сделать это невозможно. Гарантируется, что будет не более двух запросов второго вида.
\InputFile
Первая строка содержит два числа \textbf{n} и \textbf{m} (\textbf{1} ≤ \textbf{n} ≤ \textbf{10^5}, \textbf{1} ≤ \textbf{m} ≤ \textbf{10^5}). Каждая из следующих \textbf{m} строк содержит два целых числа \textbf{a} и \textbf{b}. Если \textbf{a} = \textbf{1}, то \textbf{b} равно размеру объекта, на который следует выделить память. Если \textbf{a} = \textbf{2}, то \textbf{b} равно индексу уже обработанного запроса и означает, что следует освободить объект, выделенный тем запросом. Гарантируется корректность входных данных, то есть Вас не будут просить удалить уже удаленный объект и так далее.
\OutputFile
Если выполнить все запросы невозможно, выведите слово “\textbf{IMPOSSIBLE}” (без кавычек). Иначе для каждого запроса первого типа (когда \textbf{a} = \textbf{1}) вывести в отдельной строке одно число - позицию первого байта памяти, выделенной под объект. Байты в памяти нумеруются с \textbf{0}. Если существует несколько решений, то вывести любое.
Входные данные #1
10 5 1 5 1 5 2 2 1 5 2 1
Выходные данные #1
5 0 0