F. База отдыха
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

База отдыха приглашает на летние каникулы классы школ размещение в прибрежных домиках с видом на море. Всего на базе отдыха $$$N$$$ домиков. Автоматическая система бронирования позволяет производить определенные операции управления размещением в домиках автоматически. Команды системы приведены ниже:

Order $$$Name$$$ $$$M$$$ — забронировать $$$M$$$ домиков для группы детей с названием $$$Name$$$. Гарантируется, что все названия групп уникальны. В ответ на эту команду система выводит номера домиков, которые система забронировала для этой группы детей. При этом система обязана выделить группе школьников как можно ближе расположенные друг к другу свободные домики, а первый из них — это первый свободный на побережье дом. Номера домиков разделены пробелом.

Cancel $$$Name$$$ — отмена заказа для группы детей $$$Name$$$. После этой команды те номера домов, в которых предполагалась проживание группы школьников становятся свободными для бронирования. Гарантируется, что команды на отмену заказов поступают в систему в точно таком же порядке, в котором они поступали для бронирования.

Период бронирования начинается сегодня и все номера домиков свободны. Ожидается подача $$$K$$$ запросов. Система должна работать бесперебойно, обеспечивая быстрые ответы на вводимые команды. В конце работы программы нужно вывести номера всех свободных домиков, которые еще можно предложить школьникам после обработки всех запросов.

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

В первой строке вводятся целые числа $$$N$$$ и $$$K$$$ — изначальное количество домиков, а также количество запросов ($$$1 \le N, K \le 10^5$$$).

Затем следуют $$$K$$$ строк — сами запросы.

Если сейчас подается запрос первого типа, то вводится Order $$$Name$$$ $$$M$$$, где $$$Name$$$ — название группы детей, а $$$M$$$ — количество домиков, которое надо забронировать. Гарантируется, что на текущий момент свободно хотя бы $$$M$$$ домиков.

Если сейчас подается запрос второго типа, то вводится Cancel $$$Name$$$, где $$$Name$$$ — название группы детей. Гарантируется, что в этот момент отменены заказы для всех групп, для которых они поступили раньше. Также гарантируется, что для этой группы заказ все еще не отменен.

Гарантируется, что сумма длин всех имен не превосходит $$$10^6$$$, а также сумма $$$M$$$ по всем запросам не превышает $$$10^6$$$.

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

Для каждого запроса первого типа выведите, какие домики будут забронированы для этой группы на момент запроса. Домики выводите в отсортированном порядке.

После всех запросов выведите все домики, которые остались не забронированы, тоже в отсортированном порядке.

Пример
Входные данные
5 3
Order dandelion 3
Order pear 1
Cancel dandelion
Выходные данные
1 2 3 
4 
1 2 3 5
Примечание

Обратите внимание на то, что решения, отправленные на pypy могут работать быстрее, чем решения, отправленные на python.

Также при отправке на python/pypy в этой задаче стоит использовать быстрый ввод. Для этого добавьте в начало кода следующие строчки:


import sys
def input(): return sys.stdin.readline()