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.
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
    rt.pull()

    u.splay()
    assert(not u.children[1])

def solution():
    n, q = map(int, raw_input().strip().split())
    p = map(lambda x: int(x)-1, raw_input().strip().split())
    nodes = [None]*n
    lookup = [False]*n
    for i in xrange(n):
        if lookup[i]:
            continue
        j = i
        v = []
        while not lookup[j]:
            v.append(j)
            lookup[j] = True
            j = p[j]
        build(v, 0, len(v)-1, nodes)
    result = []
    for _ in xrange(q):
        op, x, y = map(int, raw_input().strip().split())
        x -= 1
        if op == 1:
            y -= 1
            u, v = nodes[x], nodes[y]
            u.splay()
            cano(u)
            v.splay()
            if not u.parent:
                cano(v)
                u.children[1] = v
                v.parent = u
                u.pull()
            else:
                v.children[1].parent = None
                v.children[1] = None
                v.pull()
        else:
            u = nodes[x]
            u.splay()
            s = u.size
            j = u.children[0].size if u.children[0] else 0
            j = (j+y) % s
            u = select(u, j)
            u.splay()
            result.append(u.v+1)
    return "\n".join(map(str, result))

print '%s' % solution()