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: /*
  stream Butter!
  eggyHide eggyVengeance
  I need U
  xiao rerun when
   */
  import static java.lang.Math.*;
  import java.util.*;
  import java.io.*;
  import java.math.*;
  
  public class x1619H
  {
      public static final int SQRT = 110;
      public static void main(String hi[]) throws Exception
      {
          BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));
          StringTokenizer st = new StringTokenizer(infile.readLine());
          int N = Integer.parseInt(st.nextToken());
          int Q = Integer.parseInt(st.nextToken());
          int[] arr = readArr(N, infile, st);
          for(int i=0; i < N; i++)
              arr[i]--;
          int[] inverse = new int[N];
          for(int i=0; i < N; i++)
              inverse[arr[i]] = i;
          int[] step = new int[N];
          for(int i=0; i < N; i++)
          {
              step[i] = i;
              for(int k=0; k < SQRT; k++)
                  step[i] = arr[step[i]];
          }
          StringBuilder sb = new StringBuilder();
          while(Q-->0)
          {
              int[] line = readArr(3, infile, st);
              int type = line[0];
              if(type == 1)
              {
                  int x = line[1]-1;
                  int y = line[2]-1;
                  arr[x] = (arr[x]^arr[y])^(arr[y]=arr[x]);
                  inverse[arr[x]] = (inverse[arr[x]]^inverse[arr[y]])^(inverse[arr[y]]=inverse[arr[x]]);
                  int dest = x;
                  for(int k=0; k < SQRT; k++)
                      dest = arr[dest];
                  int curr = x;
                  for(int k=0; k < SQRT; k++)
                  {
                      step[curr] = dest;
                      dest = inverse[dest];
                      curr = inverse[curr];
                  }
                  dest = y;
                  for(int k=0; k < SQRT; k++)
                      dest = arr[dest];
                  curr = y;
                  for(int k=0; k < SQRT; k++)
                  {
                      step[curr] = dest;
                      dest = inverse[dest];
                      curr = inverse[curr];
                  }
              }
              else
              {
                  int curr = line[1]-1;
                  while(line[2] >= SQRT)
                  {
                      curr = step[curr];
                      line[2] -= SQRT;
                  }
                  while(line[2]-->0)
                      curr = arr[curr];
                  sb.append((curr+1)+"\n");
              }
          }
          System.out.print(sb);
      }
      public static int[] readArr(int N, BufferedReader infile, StringTokenizer st) throws Exception
      {
          int[] arr = new int[N];
          st = new StringTokenizer(infile.readLine());
          for(int i=0; i < N; i++)
              arr[i] = Integer.parseInt(st.nextToken());
          return arr;
      }
  }