Дана перестановка \(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\) раз.
Выходные данные
Для каждого запроса второго типа выведите одно целое число в новой строке — ответ на этот запрос.
Примечание
В первом примере \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 4
5 3 4 2 1
2 3 1
2 1 2
1 1 3
2 1 2
|
4
1
2
|
|
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
|