给你一个 $$$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 = p_i$$$ $$$k$$$ 次,则打印 $$$i$$$ 将变成的数字。
输入
第一行包含两个整数 $$$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$$$) — 第二种类型查询。
保证至少有一个第二类查询。
输出
对于每个第二类查询,在新行中打印一个整数 - 回答此查询。
示例
输入 #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
注意
在第一个示例中 $$$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$$$。