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: // package c1619;
  
  import java.io.File;
  import java.lang.invoke.MethodHandles;
  import java.util.ArrayList;
  import java.util.Arrays;
  import java.util.Collections;
  import java.util.List;
  import java.util.Random;
  import java.util.Scanner;
  
  //
  // Codeforces Round #762 (Div. 3) 2021-12-20 06:35
  // H. Permutation and Queries
  // https://codeforces.com/contest/1619/problem/H
  // time limit per test 4 seconds; memory limit per test 256 megabytes
  // public class Pseudo for 'Source should satisfy regex [^{}]*public\s+(final)?\s*class\s+(\w+).*'
  //
  // 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.
  //
  // Example
  /*
  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.
  //
  public class C1619H {
    static final int MOD = (int)1e9+7;
    static final Random RAND = new Random();
  
    // Time limit exceeded on test 13
    static class TestCase {
      int n;
      int q;
      int[] perm;
      int[][] queries;
      // lids[i] is loop id of i
      int[] lids;
  
      // lens[i] is the size of loop i
      int[] lens;
  
      static class ListNode {
        int v;
        ListNode prev;
        ListNode next;
  
        public ListNode(int v) {
          this.v = v;
        }
      }
  
      List<ListNode> nodes = new ArrayList<>();
  
      TestCase(int[] perm, int[][] queries) {
        this.n = perm.length - 1;
        this.q = queries.length;
        this.perm = new int[n + 1];
        System.arraycopy(perm, 0, this.perm, 0, n + 1);
        this.queries = queries;
  
        this.lids = new int[n+1];
        this.lens = new int[n+1];
        for (int i = 0; i <= n; i++) {
          nodes.add(new ListNode(i));
        }
  
        for (int i = 1; i <= n; i++) {
          int v = perm[i];
          if (lids[v] > 0) {
            continue;
          }
          ListNode head = nodes.get(v);
          ListNode tail = head;
          lids[v] = v;
          int w = perm[v];
          int len = 1;
          while (w != v) {
            lids[w] = v;
            len++;
            ListNode curr = nodes.get(w);
            tail.next = curr;
            curr.prev = tail;
            tail = curr;
            w = perm[w];
          }
          tail.next = head;
          head.prev = tail;
          lens[v] = len;
        }
        // show();
        // System.out.format("lens: %s\n", Arrays.toString(lens));
      }
  
      int[] solve() {
        int m = 0;
        for (int[] query : queries) {
          if (query[0] == 2) {
            m++;
          }
        }
        int[] ans = new int[m];
        int idx = 0;
        for (int[] query : queries) {
          if (query[0] == 1) {
            int x = query[1];
            int y = query[2];
            int t = perm[x];
            perm[x] = perm[y];
            perm[y] = t;
            handleSwap(perm[x], perm[y]);
          } else {
            ans[idx] = handlePrint(query[1], query[2]);
            idx++;
          }
        }
        return ans;
      }
  
      void handleSwap(int x, int y) {
        ListNode nodex = nodes.get(x);
        ListNode nodey = nodes.get(y);
        if (lids[x] == lids[y]) {
          // x and y in the same loop
          //   A -> B -> C -> D -> E -> F -> G -> H -> I -> A
          //             ^              ^
          //             x              y
          // After:
          //   C -> D -> E -> C
          //   F -> G -> H -> I -> A -> B -> F
          ListNode tailx = nodey.prev;
          ListNode taily = nodex.prev;
  
          nodex.prev = tailx;
          tailx.next = nodex;
  
          nodey.prev = taily;
          taily.next = nodey;
  
          {
            ListNode t = nodex;
            int len = 0;
            while (true) {
              lids[t.v] = x;
              len++;
              t = t.next;
              if (t == nodex) {
                break;
              }
            }
            lens[x] = len;
          }
  
          {
            ListNode t = nodey;
            int len = 0;
            while (true) {
              lids[t.v] = y;
              len++;
              t = t.next;
              if (t == nodey) {
                break;
              }
            }
            lens[y] = len;
          }
        } else {
          // x and y in different loop:
          //   A -> B -> C -> D -> E -> A
          //        ^
          //        x
          //   P -> Q -> R -> S -> P
          //                  ^
          //                  y
          //   B -> C -> D -> E -> A -> S -> P -> Q -> R -> B
          ListNode tailx = nodex.prev;
          ListNode taily = nodey.prev;
          int len = 0;
          ListNode t = nodex;
          while (true) {
            lids[t.v] = x;
            len++;
            t = t.next;
            if (t == nodex) {
              t = nodey;
            } else if (t == nodey) {
              break;
            }
          }
          tailx.next = nodey;
          nodey.prev = tailx;
          taily.next = nodex;
          nodex.prev = taily;
          lens[x] = len;
        }
        // show();
      }
  
      int handlePrint(int i, int k) {
        ListNode node = nodes.get(i);
        // System.out.format("  print %d %d\n", i, k);
        int offset = k % lens[lids[i]];
        for (int j = 0; j < offset; j++) {
          node = node.next;
        }
        return node.v;
      }
  
      void show() {
        for (int i = 1; i <= n; i++) {
          ListNode v = nodes.get(i);
          StringBuilder sb = new StringBuilder();
          ListNode w = v;
          while (true) {
            sb.append(w.v);
            sb.append(' ');
            w = w.next;
            if (w == v) {
              break;
            }
          }
          System.out.format("%3d: %s\n", i, sb.toString());
        }
        System.out.println(Arrays.toString(lids));
      }
    }
  
    // 49 seconds for n = q = 100000
    static void doTest() {
      long t0 = System.currentTimeMillis();
      int n = 20000;
      int q = 20000;
      List<Integer> nums = new ArrayList<>();
      for (int i = 1; i <= n; i++) {
        nums.add(i);
      }
      Collections.shuffle(nums);
      int[] perm = new int[n+1];
      for (int i = 1; i <= n; i++) {
        perm[i] = nums.get(i-1);
      }
      int[][] queries = new int[q][3];
      for (int i = 0; i < q; i++) {
        queries[i][0] = RAND.nextBoolean() ? 1 : 2;
        queries[i][1] = 1 + RAND.nextInt(n);
        queries[i][2] = 1 + RAND.nextInt(n);
        while (queries[i][2] == queries[i][1]) {
          queries[i][2] = 1 + RAND.nextInt(n);
        }
      }
      TestCase tc = new TestCase(perm, queries);
      int[] ans = tc.solve();
      System.out.println(trace(ans));
      System.out.format("%d msec\n", System.currentTimeMillis() - t0);
      System.exit(0);
    }
  
    static class TestCaseEx {
      int n;
      int[][] queries;
      int[] l;
      int[] r;
      int[] l300;
      int[] r300;
  
      TestCaseEx(int[] perm, int[][] queries) {
        this.n = perm.length - 1;
        this.queries = queries;
        int n = perm.length - 1;
        this.l = new int[n+1];
        this.r = new int[n+1];
        this.l300 = new int[n+1];
        this.r300 = new int[n+1];
        for (int i = 1; i <= n; i++) {
          r[i] = perm[i];
          l[r[i]] = i;
        }
        int j;
        int k;
        for (int i = 1; i <= n; i++) {
          for(j=1, k=i; j <= n; j++) {
            k = r[k];
          }
          r300[i]=k;
          l300[k]=i;
        }
      }
  
      int[] solve() {
        int m = 0;
        for (int[] query : queries) {
          if (query[0] == 2) {
            m++;
          }
        }
        int[] ans = new int[m];
        int idx = 0;
        for (int[] query : queries) {
          int x = query[1];
          int y = query[2];
          if (query[0] == 1) {
            int t = r[x];
            r[x] = r[y];
            r[y] = t;
            l[r[x]] = x;
            l[r[y]] = y;
            work(x);
            work(y);
          } else {
            while (y > n) {
              x = r300[x];
              y -= n;
            }
            for (int i = 0; i < y; i++) {
              x = r[x];
            }
            ans[idx] = x;
            idx++;
          }
        }
        return ans;
      }
  
      void work(int x) {
        int i;
        int k;
        int k2;
        for(i = 1, k = x; i < n; i++) {
          k = l[k];
        }
        for(i=1, k2=r[x]; i <= n; i++){
          r300[k] = k2;
          l300[k2] = k;
          k = r[k];
          k2 = r[k2];
        }
      }
    }
  
    public static final int SQRT = 50;
  
    // Based on https://codeforces.com/contest/1619/submission/140615425
    static int[] solve(int[] perm, int[][] queries) {
      int n = perm.length - 1;
      int[] arr = new int[n];
      for (int i = 0; i < n; i++) {
        arr[i] = perm[i + 1] - 1;
      }
      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]];
        }
      }
      int q = queries.length;
      int len = 0;
      for (int i = 0; i < q; i++ ) {
        if (queries[i][0] == 2) {
          len++;
        }
      }
      int[] ans = new int[len];
      int idx = 0;
      for (int i = 0; i < q; i++ ) {
        if (queries[i][0] == 1) {
          int x = queries[i][1] - 1;
          int y = queries[i][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 = queries[i][1] - 1;
          int k = queries[i][2];
          while (k >= SQRT) {
            curr = step[curr];
            k -= SQRT;
          }
          // --> is just a conjunction of the operators -- and  >.
          // i --> 0 becomes effectively i > 0; i--;
          while (k-->0) {
            curr = arr[curr];
          }
          ans[idx++] = curr + 1;
        }
      }
      return ans;
    }
  
    public static void main(String[] args) {
      // doTest();
      Scanner in = getInputScanner();
      int n = in.nextInt();
      int q = in.nextInt();
      int[] perm = new int[n + 1];
      for (int i = 1; i <= n; i++) {
        perm[i] = in.nextInt();
      }
      int[][] queries = new int[q][3];
      for (int i = 0; i < q; i++) {
        queries[i][0] = in.nextInt();
        queries[i][1] = in.nextInt();
        queries[i][2] = in.nextInt();
      }
      int[] ans = solve(perm, queries);
      System.out.println(trace(ans));
      in.close();
    }
  
    static Scanner getInputScanner() {
      try {
        final String USERDIR = System.getProperty("user.dir");
        final String CNAME = MethodHandles.lookup().lookupClass().getSimpleName();
        final File fin = new File(USERDIR + "/io/c" + CNAME.substring(1,5) + "/" + CNAME + ".in");
        return fin.exists() ? new Scanner(fin) : new Scanner(System.in);
      } catch (Exception e) {
        return new Scanner(System.in);
      }
    }
  
    static String trace(int[] arr) {
      StringBuilder sb = new StringBuilder();
      for (int v : arr) {
        sb.append(v);
        sb.append('\n');
      }
      return sb.toString();
    }
  }
  