Permutation and Queries

题意翻译

## 题目描述 给定由 $1 \sim n$ 构成的排列 $p$，有两种操作: - `1 x y`：交换 $p_{x}$ 和 $p_{y}$。 - `2 i k`：给出 $i$ 的初始值，令 $i \gets p_{i}$ 执行 $k$ 次，最后输出 $i$。 至少有一个第二类操作。 **【输入格式】** 第一行包含两个整数 $n, q$（$1 \le n,q \le 10^{5}$），分别表示数的个数和操作次数。 第二行包含 $n$ 个整数 $q_{1}, q_{2}, \ldots, q_{n}$。 接下来的 $q$ 行每行包含三个整数，表示一种操作。 **【输出格式】** 每行一个整数，表示每一个第二类查询的结果。

题目描述

You are given a permutation $ p $ of $ n $ elements. A permutation of $ n $ elements is an array of length $ n $ containing each integer from $ 1 $ to $ n $ exactly once. For example, $ [1, 2, 3] $ and $ [4, 3, 5, 1, 2] $ are permutations, but $ [1, 2, 4] $ and $ [4, 3, 2, 1, 2] $ are not permutations. You should perform $ q $ queries. There are two types of queries: - $ 1 $ $ x $ $ y $ — swap $ p_x $ and $ p_y $ . - $ 2 $ $ i $ $ k $ — print the number that $ i $ will become if we assign $ i = p_i $ $ k $ times.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ q $ ( $ 1 \le n, q \le 10^5 $ ). The second line contains $ n $ integers $ p_1, p_2, \dots, p_n $ . Each of the next $ q $ lines contains three integers. The first integer is $ t $ ( $ 1 \le t \le 2 $ ) — type of query. If $ t = 1 $ , then the next two integers are $ x $ and $ y $ ( $ 1 \le x, y \le n $ ; $ x \ne y $ ) — first-type query. If $ t = 2 $ , then the next two integers are $ i $ and $ k $ ( $ 1 \le i, k \le n $ ) — second-type query. It is guaranteed that there is at least one second-type query.

输出格式

For every second-type query, print one integer in a new line — answer to this query.

输入输出样例

输入样例 #1

5 4
5 3 4 2 1
2 3 1
2 1 2
1 1 3
2 1 2

输出样例 #1

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

输出样例 #2

3
5
4
2
3
3
3
1

说明

In the first example $ p = \{5, 3, 4, 2, 1\} $ . The first query is to print $ p_3 $ . The answer is $ 4 $ . The second query is to print $ p_{p_1} $ . The answer is $ 1 $ . The third query is to swap $ p_1 $ and $ p_3 $ . Now $ p = \{4, 3, 5, 2, 1\} $ . The fourth query is to print $ p_{p_1} $ . The answer is $ 2 $ .