Egzamin

Limit czasu: 0.5s | Limit pamięci: 32MB

Jaś, a raczej pan Jan, jest egzaminatorem. Dziś przeprowadza egzamin ze znajomości języka C++ na poziomie C2. Niestety na dworze pada grad, są trzy metry śniegu i burza piaskowa, więc uczestnicy się spóźniają. Jednak egzamin jest trudny, więc nikt nie wychodzi przed czasem.

W sali stoi bardzo duży okrągły stół. Jaś przechadza się wokół stołu. Kiedy przychodzi jakiś nowy uczestnik, na początku otrzymuje reprymendę od Jasia. Następnie Jaś usadza nowego uczestnika po uczestniku przy którym aktualnie stoi, ale przed następnym uczestnikiem (pierwsza osoba siada gdziekolwiek).

Jaś podejrzewa niektórych uczestników o ściąganie. Jeżeli stoi aktualnie przy jakimś uczestniku i widzi, że jego intencje mogą nie być czyste, potajemnie przypina mu do ubrania kamerę, aby widzieć jego ręce i laptop. Co jakiś czas Jaś będzie chciał sprawdzić co jest wyświetlane na laptopie, na który wskazuje $y$-ta w kolejności chronologicznej zamontowana kamera.

Na laptopach uczestników wyświetlane są numery zadań, które mają rozwiązywać. Początkowo na laptopie uczestnika wyświetlone jest $0$. Kiedy Jaś stoi przy jakimś uczestniku i widzi, że zadanie jest dla niego zbyt łatwe lub zbyt trudne może zmienić numer zadania wyświetlany na jego monitorze.

Ty w tym całym przedsięwzięciu masz najtrudniejsze zadanie. Musisz obsłużyć te wszystkie zdarzenia.

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę $n$ – liczbę zdarzeń. Następne $n$ wierszy zawiera opisy zdarzeń w następującym formacie:

• „n” – Jaś przechodzi do następnego uczestnika
• „a” – przychodzi nowy uczestnik, Jaś daje mu reprymendę, usadza go, a następnie do niego przechodzi
• „c” – Jaś przypina kamerę do ubrania uczestnika przy którym aktualnie stoi
• „t $x$” – Jaś zmienia numer zadania uczestnika przy którym aktualnie stoi na $x$
• „p $y$” – Jaś chce dowiedzieć się jaki numer jest wyświetlany na laptopie, na który wskazuje $y$-ta w kolejności chronologicznej zamontowana kamera

Wyjście

Na wyjściu powinno znaleźć się tyle wierszy, ile było zdarzeń typu „p $y$” na wejściu. W każdym wierszu powinna znaleźć się jedna liczba – liczba wyświetlana na laptopie, na który wskazuje $y$-ta w kolejności chronologicznej zamontowana kamera.

Ograniczenia

• $1 \le n \le 2\cdot 10^5$
• $1 \le x \le 10^6$
• $1 \le y$ nie większe niż liczba dotychczas zamontowanych kamer
• Pierwsze zdarzenie to „a”.
• Jeden uczestnik może mieć zamontowanych wiele kamer, jeśli ma wyjątkowo nieczyste intencje.
• Pojawi się co najmniej jedno zdarzenie „p $y$”.

Przykłady

Wejście 1

14
a
c
n
p 1
t 3
p 1
a
a
t 7
t 2
c
n
p 2
p 1

Wyjście 1

0
3
2
3