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: import java.io.*;
  import java.util.*;
   
  public class Solution extends PrintWriter {
      
      
      void solve() {
          int n = sc.nextInt();
          int q = sc.nextInt();
          int[] p = new int[n];
          for(int i = 0; i < n; i++) p[i] = sc.nextInt()-1;
          boolean[] done = new boolean[n];
          Node<Integer>[] nodes = new Node[n];
          for(int i = 0; i < n; i++) nodes[i] = new Node<>(i);
          for(int i = 0; i < n; i++) {
              if(done[i]) continue;
              ArrayDeque<Integer> cycle = new ArrayDeque<>();
              int u = i;
              while(!done[u]) {
                  cycle.addFirst(u);
                  done[u] = true;
                  u = p[u];
              }
              SplayTree<Integer> st = null;
              for(int x : cycle) {
                  if(st == null) st = new SplayTree<>(nodes[x]);
                  else st.join(new SplayTree<>(nodes[x]));
              }
          }
          for(int qq = 0; qq < q; qq++) {
              int t = sc.nextInt();
              if(t == 1) {
                  int x = sc.nextInt()-1;
                  int y = sc.nextInt()-1;
                  SplayTree<Integer> st_x = new SplayTree<Integer>(nodes[x]);
                  if(nodes[x] == st_x.find_root(nodes[y])){
                      SplayTree<Integer> x1 = st_x;
                      SplayTree<Integer> x3 = new SplayTree<Integer>(x1.split_at(nodes[x]));
                      Node<Integer> root_y = x3.find_root(nodes[y]);
                      if(root_y == x3.root) {                        
                          x3 = new SplayTree<Integer>(x3.split_at(nodes[y]));
                      } else {
                          x1.split_at(nodes[y]);
                      }
                      x3.join(x1);
                  } else {
                      SplayTree<Integer> x2 = new SplayTree<>(st_x.split_at(nodes[x]));
                      SplayTree<Integer> x1 = st_x;                    
  
                      SplayTree<Integer> st_y = new SplayTree<Integer>(nodes[y]);
                      SplayTree<Integer> y2 = new SplayTree<>(st_y.split_at(nodes[y]));
                      SplayTree<Integer> y1 = st_y;
                      
                      y2.join(x1);
                      y1.join(y2);
                      x2.join(y1);
                  }
              } else {
                  int i = sc.nextInt()-1;
                  int k = sc.nextInt();
                  SplayTree<Integer> st = new SplayTree<Integer>(nodes[i]);
                  int size = st.size();
                  int pos = st.pos(nodes[i]);
                  k += pos;
                  Node<Integer> ans = st.find((k % size) + 1);
                  println(ans.val+1);
              }
                      
          }
      }
      
      class SplayTree<T> {
          
          Node<T> root;
          
          public SplayTree(Node<T> node) {
              if(node == null) return;
              splay(node);
          }
          
          Node<T> find_root(Node<T> node){
              while(node.p != null) node = node.p;
              return node;
          }
          
          int size(Node<T> node) {
              return node == null?0:node.sz;
          }
          int size() {
              return size(root);
          }
          
          void rotate(Node<T> node) {
              Node<T> p = node.p;
              int side = node.p.ch[0] == node?0:1;
              if (p.p != null) p.p.attach(p.side(), node);
              else node.p = null;
              p.attach(side, node.ch[1-side]);
              node.attach(1-side, p);
              p.update();
              node.update();
          }
          
          void splay(Node<T> node) {
              node.update();
              while(node.p != null) {
                  if (node.p.p != null) {
                      rotate((node.side() == node.p.side() ? node.p: node));
                  }
                  rotate(node);
              }
              root = node;
          }
          
          Node<T> find(int v) {
              if (root == null) return root;
              Node<T> x = root;
              while (true) {
                  //x->prop();
                  Node<T> next = x.ch[0];
                  int cnt = size(next)+1;
                  if (cnt == v) break;
                  else if(cnt < v){
                      v -= cnt;
                      next = x.ch[1];
                  }
                  x = next;
              }
              splay(x);
              return root;
          }
          
          int pos(Node<T> node) {
              splay(node);
              return size(root.ch[0]);
          }
          /*
          Node<T> split_at(Node<T> node) {
              splay(node);
              Node<T> l = root.ch[0];
              root.ch[0] = null;
              if (l != null) l.p = null;
              root.update();
              return l;
          }*/
          
          Node<T> split_at(Node<T> node) {
              splay(node);
              Node<T> r = root.ch[1];
              root.ch[1] = null;
              if (r != null) r.p = null;
              root.update();
              return r;
          }
          
          void join(SplayTree<T> l) { 
              if (size() == 0) {
                  Node<T> temp = root;
                  root = l.root;
                  l.root = temp;
              }
              if (size() == 0 || l.size() == 0) return;
              Node<T> x = l.root;
              while (true) {
                 // x->prop();
                  if (x.ch[1] == null) break;
                  x = x.ch[1];
              }
              l.splay(x);
              //root.prop();
              root.update();
              x.ch[1] = root;
              x.ch[1].p = x;
              root = l.root;
              l.root = null;
              root.update();
          }
      }
   
      class Node<T> {
          int sz;
          T val;
          Node<T>[] ch;
          Node<T> p;
          public Node(T key) {
              ch = new Node[2];
              this.val = key;
              this.sz = 1;
          }
          
          void update() {
              this.sz = 1;
              for (int i = 0; i < 2; i++) 
                  if (ch[i] != null) {
                      this.sz += ch[i].sz;
                  }
          }
          
          int side() {
              return p.ch[0] == this?0:1;
          }
          
          void attach(int side, Node<T> new_) {
              if (new_ != null) new_.p = this;
              ch[side] = new_;
          }
      }
      
          
  //  Main() throws FileNotFoundException { super(new File("output.txt")); }
  //  InputReader sc = new InputReader(new FileInputStream("test_input.txt"));
    Solution() { super(System.out); }
    InputReader sc = new InputReader(System.in);
    static class InputReader {
        InputReader(InputStream in) { this.in = in; } InputStream in;
        
        private byte[] buf = new byte[16384];
        private int    curChar;
        private int    numChars;
        
   
        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = in.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }
   /*
        private String nextLine() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isEndOfLine(c));
            return res.toString();
        }*/
   
        public String nextString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }
   
        public long nextLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }
   
        public int nextInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }
   
        private boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
   
        private boolean isEndOfLine(int c) {
            return c == '\n' || c == '\r' || c == -1;
        }
    }
   
      public static void main(String[] $) {
          new Thread(null, new Runnable() {
              public void run() {
                  long start = System.nanoTime();
                  try {Solution solution = new Solution(); solution.solve(); solution.flush();} 
                  catch (Exception e) {e.printStackTrace(); System.exit(1);}
                  System.err.println((System.nanoTime()-start)/1E9);
              }
          }, "1", 1 << 27).start();
   
      }
  }