Журнал квестов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Уже даже только среди племен Тенакт и Утару нашлось невообразимое количество людей, которые дали Элой некоторые квесты, поэтому Элой завела журнал, чтобы ничего не забыть. Журнал представляет из себя очередь, то есть чем раньше Элой получила некоторый квест, тем раньше она отправится его выполнять. Помимо этого, у каждого квеста есть приоритет, обозначающий его важность. Чем меньше значение приоритета, тем более важным является квест.

Таким образом, требуется обрабатывать два типа запросов:

К сожалению, журнал не бесконечный, поэтому иногда Элой вычеркивает из него квесты, которые не так важны на данный момент, чтобы освободить место. Квест считается неважным, если перед ним в очереди есть хотя бы два квеста со строго меньшим приоритетом.

В тот момент, когда в конец очереди добавляется новый квест с приоритетом $$$p_i$$$, и выясняется, что он является неважным, Элой проверяет, не стоит ли вычеркнуть часть квестов. Для этого она находит два квеста в очереди с самыми маленькими значениями приоритета (обозначим эти значения за $$$pm_1$$$ и $$$pm_2$$$) и вычисляет величину $$$(p_i - pm_1) \cdot (p_i - pm_2)$$$. Если эта величина оказывается строго больше заранее выбранной величины $$$X$$$, Элой вычеркивает из журнала все неважные квесты (включая только что добавленный). Порядок оставшихся квестов в очереди при этом сохраняется.

Помогите Элой обработать $$$n$$$ последовательных событий с журналом. Для каждого события вида «выполнить квест» сообщите ей идентификатор квеста, который следует выполнять следующим.

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

В первой строке ввода через пробел даны два целых числа $$$n$$$ и $$$X$$$ — количество запросов и константа, участвующая в критерии очистки журнала ($$$1 \leqslant n \leqslant 2 \cdot 10^6$$$; $$$1 \leqslant X \leqslant 10^9$$$).

Далее следуют $$$n$$$ строк, в $$$i$$$-й из которых дано описание $$$i$$$-го запроса. Если первый символ в строке равен '+', за ним через пробел следуют два целых числа $$$t_j$$$ и $$$p_j$$$ — идентификатор и приоритет нового квеста, который надо добавить в конец журнала ($$$1 \leqslant t_j, p_j \leqslant 10^9$$$). Иначе, строка состоит из единственного символа '-', и в таком случае Элой выполняет первый в очереди квест.

Гарантируется, что перед каждым запросом второго типа журнал не пуст. Гарантируется, что все $$$t_j$$$ во вводе различны.

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

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

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач, а также тесты из условия успешно пройдены.

ПодзадачаБаллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
17$$$n \leqslant 8$$$; запросов типа '+' не больше $$$4$$$полная
215 $$$n \leqslant 10^5$$$; $$$p_j \leqslant p_k$$$ для всех $$$j < k$$$ полная
315$$$n \leqslant 100$$$1полная
413$$$p_j \leqslant 3$$$ для всех $$$j$$$полная
520$$$n \leqslant 2000$$$3полная
620$$$n \leqslant 10^5$$$2, 5первая ошибка
710нет1 – 6первая ошибка

Примеры

Входные данные
4 5
+ 1 3
+ 2 1
+ 3 5
-
Выходные данные
1
Входные данные
8 5
+ 1 3
+ 2 4
+ 3 7
+ 4 3
+ 5 3
-
-
-
Выходные данные
1
2
4