human
PYTHON3 solution for "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.":


 Write me a Python program to print the number that i will become if we assign i = p_i k times?
assistant
#Here is Python program to print the number that i will become if we assign i = p_i k times.
 
def main():
    
    def computeR():
        r = [0] * n
        for i, x in enumerate(p):
            r[x] = i
        return r
    
    def computeA():
        a = [0] * n
        for i in range(n):
            j = i
            for _ in range(base):
                j = p[j]
            a[i] = j
        return a
    
    def update(x, y): # swap operation
        temp = p[x]; p[x] = p[y]; p[y] = temp
        
        # for z in (x, y):
        #     for _ in range(base + 1):
        #         z = r[z]
        #     z2 = z
        #     for _ in range(base):
        #         z2 = p[z2]
        #     for _ in range(base + 2):
        #         a[z] = z2
        #         z = p[z]; z2 = p[z2]
        
        temp = r[p[x]]; r[p[x]] = r[p[y]]; r[p[y]] = temp
        # assert r == computeR() # TEST
        
        for z in (x, y):
            for _ in range(base):
                z = r[z]
            z2 = z
            for _ in range(base):
                z2 = p[z2]
            for _ in range(base + 1):
                a[z] = z2
                z = p[z]; z2 = p[z2]
        # assert a == computeA(), 'a:{} computeA:{}'.format(a, computeA()) # TEST
    
    def query(x, k):
        while k >= base:
            k -= base
            x = a[x]
        while k >= 1:
            k -= 1
            x = p[x]
        return x + 1
    
    n, m = readIntArr()
    p = readIntArr()
    for i in range(n):
        p[i] -= 1
    
    # # TEST
    # n, m = 10, 0
    # p = list(range(1, n + 1))
    # for i in range(n): p[i] -= 1
    
    base = int(n ** 0.5 + 1)
    r = computeR()
    a = computeA()
    
    # for x in range(n): # TEST
    #     for y in range(x + 1, n):
    #         update(x, y)
    
    allans = []
    for _ in range(m):
        aa, bb, cc = readIntArr()
        if aa == 1: # swap
            update(bb - 1, cc - 1)
        else: # get ans
            allans.append(query(bb - 1, cc))
    multiLineArrayPrint(allans)
    
    return

import sys
input=sys.stdin.buffer.readline #FOR READING PURE INTEGER INPUTS...