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

Input

The first line contains two integers n and q (1 ≤ n, q ≤ 10^5).

The second line contains n integers p_1, p_2, ..., p_n.

Each of the next q lines contains three integers. The first integer is t (1 ≤ t ≤ 2) — type of query. If t = 1, then the next two integers are x and y (1 ≤ x, y ≤ n.
x ≠ y) — first-type query. If t = 2, then the next two integers are i and k (1 ≤ i, k ≤ n) — second-type query.

It is guaranteed that there is at least one second-type query.

Output

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

Examples

Input

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

Output

4
1
2

Input

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

Output

3
5
4
2
3
3
3
1

Note

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.
assistant
#Here is Python code to print the number that i will become if we assign i = p_i k times.

import sys
raw_input = iter(sys.stdin.read().splitlines()).next

class Node(object):
    def __init__(self, v):
        self.v = v
        self.children = [None]*2
        self.parent = None
        self.size = 1

    def pull(self):
        self.size = 1
        if self.children[0]:
            self.size += self.children[0].size
        if self.children[1] :
            self.size += self.children[1].size

    def rotate(self):
        q = self.parent
        x = not self.pos()
        q.children[not x] = self.children[x]
        if self.children[x]:
            self.children[x].parent = q
        self.parent = q.parent
        if q.parent:
            q.parent.children[q.pos()] = self
        self.children[x] = q
        q.parent = self
        q.pull()

    def pos(self):
        return self.parent.children[1] == self

    def splay(self, g=None):
        while self.parent != g:
            if self.parent.parent != g:
                if self.pos() == self.parent.pos():
                    self.parent.rotate()
                else:
                    self.rotate()
            self.rotate()
        self.pull()

def select(t, k):
    if t.children[0]:
        if k < t.children[0].size:
            return select(t.children[0], k)
        else:
            k -= t.children[0].size
    if k == 0:
        return t
    k -= 1
    return select(t.children[1], k)

def build(v, left, right, nodes):
    if left > right:
        return None
    mid = left + (right-left)//2
    u = v[mid]
    nodes[u] = Node(u)
    nodes[u].children[0] = build(v, left , mid-1, nodes)
    nodes[u].children[1] = build(v, mid+1, right, nodes)
    for i in xrange(2):
        if nodes[u].children[i]:
            nodes[u].children[i].parent = nodes[u]
    nodes[u].pull()
    return nodes[u]

def cano(u):
    if not u.children[1]:
        return
    rm = select(u.children[1], 0)
    rm.splay(u)

    u.children[1] = None
    rm.parent = None
    u.pull()

    rt = select(u, 0)
    rt.splay()

    rt.children[0] = rm
    rm.parent = rt
   ...