description: 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.
solution: 
  def main():
      
      n, q = readIntArr()
      p = readIntArr()
      for i in range(n):
          p[i] -= 1 # make 0-index
      
      base = int(n ** 0.5 + 1)
      a = [-1] * n # a[i] is i after base operations
      r = [-1] * n # r is reverse of p, i.e. base operations back. r[p[i]] = i
      for i in range(n):
          r[p[i]] = i
          i2 = i
          for _ in range(base):
              i = p[i]
          a[i2] = i
      allans = []
      # print('initial p:{} r:{} a:{} base:{}'.format(p, r, a, base))
      for _ in range(q):
          t, x, y = readIntArr()
          if t == 1: # swap
              x -= 1; y -= 1
              temp = p[x]; p[x] = p[y]; p[y] = temp
              for z in (x, y): # re-compute base items back in O(base) time
                  for __ in range(base + 1):
                      z = r[z]
                  j = i = z
                  for __ in range(base):
                      j = p[j]
                  for __ in range(base + 2):
                      # print('i:{} j:{}'.format(i, j))
                      a[i] = j
                      i = p[i]
                      j = p[j]
              # update the reverse
              r[p[x]] = x; r[p[y]] = y
              # print('x:{} y:{} p:{} r:{} a:{}'.format(x, y, p, r, a))
              
              # re-run computation
              for z in (x, y): # re-compute base items back in O(base) time
                  for __ in range(base + 1):
                      z = r[z]
                  j = i = z
                  for __ in range(base):
                      j = p[j]
                  for __ in range(base + 2):
                      # print('i:{} j:{}'.format(i, j))
                      a[i] = j
                      i = p[i]
                      j = p[j]
                      
          else:
              i = x; k = y
              i -= 1
              while k >= base:
                  i = a[i]
                  k -= base
              while k >= 1:
                  i = p[i]
                  k -= 1
              allans.append(i + 1) # 1-index answer
      multiLineArrayPrint(allans)
                      
          
      
      return
  
  
  import sys
  input=sys.stdin.buffer.readline #FOR READING PURE INTEGER INPUTS (space separation ok)
  # input=lambda: sys.stdin.readline().rstrip("\r\n") #FOR READING STRING/TEXT INPUTS.
  
  def oneLineArrayPrint(arr):
      print(' '.join([str(x) for x in arr]))
  def multiLineArrayPrint(arr):
      print('\n'.join([str(x) for x in arr]))
  def multiLineArrayOfArraysPrint(arr):
      print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))
   
  def readIntArr():
      return [int(x) for x in input().split()]
  # def readFloatArr():
  #     return [float(x) for x in input().split()]
   
  def makeArr(defaultValFactory,dimensionArr): # eg. makeArr(lambda:0,[n,m])
      dv=defaultValFactory;da=dimensionArr
      if len(da)==1:return [dv() for _ in range(da[0])]
      else:return [makeArr(dv,da[1:]) for _ in range(da[0])]
   
  def queryInteractive(a, b, c):
      print('? {} {} {}'.format(a, b, c))
      sys.stdout.flush()
      return int(input())
   
  def answerInteractive(ansArr):
      print('! {}'.format(' '.join([str(x) for x in ansArr])))
      sys.stdout.flush()
   
  inf=float('inf')
  # MOD=10**9+7
  # MOD=998244353
  
  from math import gcd,floor,ceil
  import math
  # from math import floor,ceil # for Python2
   
  for _abc in range(1):
      main()