Statement is not available in English language
L. Звезда в Отеле
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Как известно, в Отеле скучно не бывает: то фуршет, то номерки какие-то загадочные. А вот сейчас, для гостей опять подготовили нечто невероятное: приезжает Звезда.

Звезды — народ причудливый, вот например, Звезда, приехавшая в Отель, боится больших скоплений людей, поэтому поклонников на автограф-сессии будет принимать в специальном кабинете и только по одному, все же остальные гости будут ожидать в зале. И все бы хорошо, человечество давно придумало очереди, только вот во время сессии проходит фуршет, поэтому все разбредутся по залу и никакой очереди в ее привычном понимании устроить не получится и САО (служба администрирования очередей) решила обратиться к вам.

Вас просят написать систему учета людей, которая должна уметь выводить номер текущего первого в очереди гостя, добавлять людей в очередь и удалять из нее. Но мало того, что неразбериха с фуршетом, САО ещё и по неизвестной нам причине поощряет использование знакомств и связей в личных корыстных целях (в народе «блат»): если в зал приходит человек $$$x$$$, то он хочет найти своего друга $$$y$$$ и, если $$$y$$$ находится в зале, то $$$x$$$ в очереди становится прямо за ним, иначе $$$x$$$ помещается системой в конец очереди. Также может произойти такое, что гостю надоело ждать и тогда он просто уходит из зала ожидания и исключается из очереди.

Конечно, обработка событий по видео-камерам — увлекательный процесс, но САО решили, что проще будет дать уже готовую последовательность данных. Итак, вашей системе нужно обрабатывать следующие запросы:

  1. in x y — в зал фуршета приходит гость с номером $$$x$$$, который дружит с гостем номер $$$y$$$. Если $$$y$$$ уже находится в очереди, то $$$x$$$ встает за ним, иначе в конец. Стоит отметить, что гости очень восхищаются Звездой и могут приходить и не по одному разу.
  2. out x — гостю под номером $$$x$$$ надоело ждать и он уходит (гарантируется, что в данный момент гость с таким номером находится в зале).
  3. check — Звезда готова дать очередной автограф и САО хочет узнать, кто первый в очереди (после этого счастливец получит автограф и уйдет по своим делам). Если очередь пуста, выведите $$$-1$$$.
Входные данные

В первой строке вводится единственное натуральное число $$$q$$$ ($$$1 \leq q \leq 200\,000$$$) — количество запросов. Далее в $$$q$$$ строках вводятся вышеописанные запросы. Все числа, содержащиеся в запросах натуральные и не превосходят $$$10^8$$$.

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

На каждый запрос $$$check$$$ в отдельной строке выведете номер первого человека в очереди.

Примеры
Входные данные
10
in 1 1
in 2 1
in 3 1
in 4 2
check
out 4
check
in 5 6
in 6 5
check
Выходные данные
1
3
2
Входные данные
10
check
in 10 5
in 9 3
in 6 7
out 6
in 5 3
in 3 4
check
in 7 2
in 2 8
Выходные данные
-1
10