AlgoLiga 2018

Zadanie finałowe w konkursie pamięciowym jest nie lada wyzwaniem dla uczestników. Grono najlepszych zawodników będzie musiało zmierzyć się z problemem kolejkowania. Trzon zadania stanowi początkowo pusta kolejka, do której przychodzą co i rusz nowe osoby na wybrane przez siebie miejsce w kolejce. Przychodzące osoby identyfikujemy kolejnymi numerami całkowitymi począwszy od 1. Żadne dwie osoby nie mogą stać w tym samym miejscu w kolejce (np. jeśli przychodzi nowa osoba na drugie miejsce w kolejce, to wszystkie osoby oprócz pierwszej muszą ją przepuścić). Pomiędzy aktualizacjami kolejki finaliści mogą być wielokrotnie odpytywani o miejsce danej osoby w kolejce lub o osobę zajmującą dane miejsce w kolejce. Wszystkie polecenia wydawane są głosowo, a zawodnicy mają do dyspozycji tylko własny umysł! Na szczęście w AlgoLidze mamy łatwiej – wystarczy napisać program rozwiązujący opisany wyżej problem.

Wejście

Pewna liczba poleceń w osobnych wierszach. Każdy wiersz składa się z dwóch liczb całkowitych dodatnich f x, oznaczających kolejno: rodzaj operacji i wartość argumentu tej operacji. Niech j oznacza aktualną liczbę osób w kolejce; początkowo j = 0.

Zdefiniowano następujące polecenia:

f = 1 oraz x ∈ [1, j + 1] - nowa osoba o numerze j + 1 wchodzi do kolejki na miejsce x;

f = 2 oraz x ∈ [1, j] - zapytanie o miejsce w kolejce zajmowane przez osobę o numerze x;

f = 3 oraz x ∈ [1, j] - zapytanie o osobę, która stoi na miejscu x w kolejce.

W pierwszym wierszu zawsze znajdzie się para liczb 1 1.

Wyjście

Dla każdego zapytania należy wypisać w pojedynczym wierszu odpowiedź.

Do kolejki przyjdzie maksymalnie 250000 osób, zaś sumaryczna liczba zapytań nie przekroczy 500000.

Przykład

Wejście:

1 1
1 2
1 1
3 1
2 1
1 3
1 2
2 2
3 2

Wyjście:

3
2
5
5