Codeforces и Polygon могут быть недоступны в период с 23 мая, 7:00 (МСК) по 23 мая, 11:00 (МСК) в связи с проведением технических работ. ×

H. Перестановка и запросы
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана перестановка $$$p$$$ из $$$n$$$ элементов. Перестановка из $$$n$$$ элементов — это массив длины $$$n$$$, в котором каждое целое число от $$$1$$$ до $$$n$$$ встречается ровно по одному разу. Например, $$$[1, 2, 3]$$$ и $$$[4, 3, 5, 1, 2]$$$ — это перестановки, но $$$[1, 2, 4]$$$ и $$$[4, 3, 2, 1, 2]$$$ — это не перестановки. Вам нужно выполнить $$$q$$$ запросов.

Есть два типа запросов:

  • $$$1$$$ $$$x$$$ $$$y$$$ — поменять местами $$$p_x$$$ и $$$p_y$$$.
  • $$$2$$$ $$$i$$$ $$$k$$$ — вывести число, которым станет $$$i$$$, если присвоить $$$i = p_i$$$ $$$k$$$ раз.
Входные данные

В первой строке находятся два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 10^5$$$).

Во второй строке находятся $$$n$$$ целых чисел $$$p_1, p_2, \dots, p_n$$$.

В каждой из следующих $$$q$$$ строк находится по три целых числа. Первое число $$$t$$$ ($$$1 \le t \le 2$$$) – тип запроса. Если $$$t = 1$$$, то следующие два целых числа — это $$$x$$$ и $$$y$$$ ($$$1 \le x, y \le n$$$; $$$x \ne y$$$) — запрос первого типа. Если $$$t = 2$$$, то следующие два целых числа — это $$$i$$$ и $$$k$$$ ($$$1 \le i, k \le n$$$) — запрос второго типа.

Гарантируется, что есть хотя бы один запрос второго типа.

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

Для каждого запроса второго типа выведите одно целое число в новой строке — ответ на этот запрос.

Примеры
Входные данные
5 4
5 3 4 2 1
2 3 1
2 1 2
1 1 3
2 1 2
Выходные данные
4
1
2
Входные данные
5 9
2 3 5 1 4
2 3 5
2 5 5
2 5 1
2 5 3
2 5 4
1 5 4
2 5 3
2 2 5
2 5 1
Выходные данные
3
5
4
2
3
3
3
1
Примечание

В первом примере $$$p = \{5, 3, 4, 2, 1\}$$$.

Первый запрос — вывести $$$p_3$$$. Ответ — $$$4$$$.

Второй запрос — вывести $$$p_{p_1}$$$. Ответ — $$$1$$$.

Третий запрос — поменять местами $$$p_1$$$ и $$$p_3$$$. Теперь $$$p = \{4, 3, 5, 2, 1\}$$$.

Четвёртый запрос — вывести $$$p_{p_1}$$$. Ответ — $$$2$$$.