CF1619H.Permutation and Queries

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.

给你一个 $n$ 个元素的排列 $p$。$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$ 执行 $k$ 次赋值 $i = p_i$ 后所得的数值。

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.

第一行包含两个整数 $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$），表示第二类查询。

保证至少存在一个第二类查询。

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

对于每个第二类查询，在新的一行中输出一个整数——该查询的答案。

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$.

在第一个例子中，$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$。