Problem description

W tym zadaniu celem jest przygotowanie algorytmu/struktury danych do zarządzania dynamiczną permutacją: pewnym ustawieniem liczb 1, 2, …, N w ciąg.

Na początku otrzymujemy ciąg π: ciąg parami różnych liczb π[1], π[2], …, π[N] z przedziału 1 do N. Następnie, należy obsłużyć operacje/zapytania następujących typów:

• zamień π[i] oraz π[j],
• wyznacz największą wartość spośród z, π[z], π[π[z]], π[π[π[z]]], …, π^k[z].

Napisz program, który wczyta początkową permutację oraz operacje i zapytania, wyznaczy odpowiedzi na wszystkie zapytania i wypisze wyniki na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, oznaczająca długość permutacji. W drugim wierszu wejścia znajduje się N parami różnych liczb naturalnych π_i, pooddzielanych pojedynczymi odstępami. W trzecim wierszu wejścia znajduje się jedna liczba naturalna Q, oznaczająca liczbę operacji/zapytań. W kolejnych Q wierszach znajdują się operacje/zapytania, po jednym w wierszu. Każde zapytanie jest postaci:

• swap x_i y_i – dla wartości 1 ≤ x_i, y_i ≤ N, wykonaj zamianę π[x_i] oraz π[y_i],
• query z_i k_i – dla wartości 1 ≤ z_i ≤ N, podaj największą wartość ze zbioru {z_i, π[z_i], π[π[z_i]], …, π^k_i[z_i]}.

Wyjście

Dla każdego zapytania query, zgodnie z kolejnością na wejściu należy wypisać odpowiedź. Odpowiedzi dla zapytań należy wypisywać w osobnych wierszach, bez dodatkowych odstępów.

Ograniczenia

1 ≤ N ≤ 100 000, 1 ≤ Q ≤ 100 000, 1 ≤ k_i ≤ N.

Przykład

5
2 3 1 5 4
7
query 2 3
query 2 1
swap 3 5
query 2 3
query 1 5
swap 5 1
query 2 1

3
3
5
5
3