Задача: Звезда в Отеле
Как известно, в Отеле скучно не бывает: то фуршет, то номерки какие-то загадочные. А вот сейчас, для гостей опять подготовили нечто невероятное: приезжает Звезда.
Звезды — народ причудливый, вот например, Звезда, приехавшая в Отель, боится больших скоплений людей, поэтому поклонников на автограф-сессии будет принимать в специальном кабинете и только по одному, все же остальные гости будут ожидать в зале. И все бы хорошо, человечество давно придумало очереди, только вот во время сессии проходит фуршет, поэтому все разбредутся по залу и никакой очереди в ее привычном понимании устроить не получится и САО (служба администрирования очередей) решила обратиться к вам.
Вас просят написать систему учета людей, которая должна уметь выводить номер текущего первого в очереди гостя, добавлять людей в очередь и удалять из нее. Но мало того, что неразбериха с фуршетом, САО ещё и по неизвестной нам причине поощряет использование знакомств и связей в личных корыстных целях (в народе <<блат>>): если в зал приходит человек \(x\), то он хочет найти своего друга \(y\) и, если \(y\) находится в зале, то \(x\) в очереди становится прямо за ним, иначе \(x\) помещается системой в конец очереди. Также может произойти такое, что гостю надоело ждать и тогда он просто уходит из зала ожидания и исключается из очереди.
Конечно, обработка событий по видео-камерам — увлекательный процесс, но САО решили, что проще будет дать уже готовую последовательность данных. Итак, вашей системе нужно обрабатывать следующие запросы:
-
in x y — в зал фуршета приходит гость с номером \(x\), который дружит с гостем номер \(y\). Если \(y\) уже находится в очереди, то \(x\) встает за ним, иначе в конец. Стоит отметить, что гости очень восхищаются Звездой и могут приходить и не по одному разу.
-
out x — гостю под номером \(x\) надоело ждать и он уходит (гарантируется, что в данный момент гость с таким номером находится в зале).
-
check — Звезда готова дать очередной автограф и САО хочет узнать, кто первый в очереди (после этого счастливец получит автограф и уйдет по своим делам). Если очередь пуста, выведите \(-1\).
Формат входных данных
В первой строке вводится единственное натуральное число \(q\) (\(1 \leq q \leq 200\,000\)) — количество запросов. Далее в \(q\) строках вводятся вышеописанные запросы. Все числа, содержащиеся в запросах натуральные и не превосходят \(10^8\).
Формат выходных данных
На каждый запрос \(check\) в отдельной строке выведете номер первого человека в очереди.
Ваш ответ: