28620번 - Журнал квестов 다국어

문제

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

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

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

• добавить в конец очереди квест с уникальным идентификатором $t_j$ и приоритетом $p_j$;
• выполнить квест, находящийся в начале очереди.

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

В тот момент, когда в конец очереди добавляется новый квест с приоритетом $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$ во вводе различны.

출력

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

제한

힌트