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: #include <bits/stdc++.h>
  using namespace std;
  using ll = long long;
  using ull = unsigned long long;
  using u32 = unsigned int;
  using db = double;
  using ld = long double;
  using pii = std::array<int, 2>;
  using pll = std::array<ll, 2>;
  const int INF = 0x3f3f3f3f;
  const long long INFll = 0x3f3f3f3f3f3f3f3f;
  namespace Fast_in {
  template <typename T>
  void in(T &x) {
    x = 0;
    bool f = false;
    char ch = getchar();
    while (!isdigit(ch)) {
      if (ch == '-') f = true;
      ch = getchar();
    }
    while (isdigit(ch)) {
      x = x * 10 + ch - '0';
      ch = getchar();
    }
    if (f) x = -x;
  }
  template <typename T>
  T in() {
    T x = 0;
    bool f = false;
    char ch = getchar();
    while (!isdigit(ch)) {
      if (ch == '-') f = true;
      ch = getchar();
    }
    while (isdigit(ch)) {
      x = x * 10 + ch - '0';
      ch = getchar();
    }
    return f ? -x : x;
  }
  template <typename T, typename... Tp>
  void in(T &x, Tp &...a) {
    in(x);
    in(a...);
  }
  template <typename T>
  void in(T *l, T *r) {
    for (; l != r; ++l) in(*l);
  }
  }  // namespace Fast_in
  using namespace Fast_in;
  namespace Fast_out {
  template <typename T>
  void out_sub(T x, char ch = '\n') {
    static int tp, sk[30];
    if (x < 0) {
      putchar('-');
      x = -x;
    }
    do {
      sk[++tp] = x % 10;
      x /= 10;
    } while (x);
    while (tp) {
      putchar(sk[tp--] + '0');
    }
    putchar(ch);
  }
  void out(int x, char ch = '\n') { out_sub(x, ch); }
  void out(ll x, char ch = '\n') { out_sub(x, ch); }
  void out(u32 x, char ch = '\n') { out_sub(x, ch); }
  void out(ull x, char ch = '\n') { out_sub(x, ch); }
  void out(db x, char ch = '\n') { printf("%.12f%c", x, ch); }
  void out(ld x, char ch = '\n') { printf("%.12Lf%c", x, ch); }
  void out(char x, char ch = '\n') { printf("%d%c", x, ch); }
  void out(char *x, char ch = '\n') { printf("%s%c", x, ch); }
  void out(string x, char ch = '\n') { printf("%s%c", x.c_str(), ch); }
  void out(pii x) { out_sub(x[0], ' '), out_sub(x[1]); }
  void out(pll x) { out_sub(x[0], ' '), out_sub(x[1]); }
  template <typename T>
  void out(vector<T> x, char ch = ' ') {
    if (x.empty()) {
      puts("");
      return;
    }
    T val = x.back();
    x.pop_back();
    for (auto i : x) out(i, ch);
    out(val);
  }
  template <typename T>
  void out(set<T> x, char ch = ' ') {
    if (x.empty()) {
      puts("");
      return;
    }
    T val = *x.rbegin();
    x.erase(--x.end());
    for (auto i : x) out(i, ch);
    out(val);
  }
  template <typename T>
  void out(T *l, T *r, char ch = ' ') {
    if (l == r) {
      puts("");
      return;
    }
    --r;
    for (; l != r; ++l) out(*l, ch);
    if (l == r) out(*l);
  }
  template <typename T, typename... Tp>
  void out(T x, Tp... a) {
    out(x, ' ');
    out(a...);
  }
  }  // namespace Fast_out
  using namespace Fast_out;
  namespace Bin {
  template <typename T>
  void out_bin(T x, char ch = '\n') {
    long long val = 1ll << 32;
    bool flg = false;
    if (x > val) {
      for (int i = 63; ~i; --i)
        if (flg)
          printf("%d", (x >> i) & 1);
        else if ((x >> i) & 1) {
          flg = true;
          printf("1");
        }
    } else {
      for (int i = 31; ~i; --i)
        if (flg)
          printf("%d", (x >> i) & 1);
        else if ((x >> i) & 1) {
          flg = true;
          printf("1");
        }
    }
    putchar(ch);
  }
  template <typename T>
  void in_bin(T &x) {
    x = 0;
    char ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) {
      x <<= 1;
      x |= ch & 1;
      ch = getchar();
    }
  }
  }  // namespace Bin
  using namespace Bin;
  struct Timer {
    int val, pre;
    Timer() {
      pre = clock();
      val = clock();
    }
    void operator()(int flg = 2) {
      if (flg == 2) val = pre;
      int now = clock();
      if (flg != 0) std::cerr << now - val << "ms\n";
      if (flg != 1) val = now;
      pre = now;
    }
  };
  Timer Time;
  template <typename T>
  void Max(T &x, T y) {
    x < y && (x = y);
  }
  template <typename T>
  void Min(T &x, T y) {
    x > y && (x = y);
  }
  template <typename T, class Func>
  void Max(T &x, T y, Func F) {
    if (x < y) {
      x = y;
      F();
    }
  }
  template <typename T, class Func>
  void Min(T &x, T y, Func F) {
    if (x > y) {
      x = y;
      F();
    }
  }
  template <typename T>
  T abss(T x) {
    return x < 0 ? -x : x;
  }
  void File(string In, string Out) {
    if (!In.empty()) freopen(In.c_str(), "r", stdin);
    if (!Out.empty()) freopen(Out.c_str(), "w", stdout);
  }
  namespace Mod {
  const int md = 998244353;
  inline int add(const int &a, const int &b) {
    int p = a + b;
    if (p >= md) p -= md;
    return p;
  }
  inline int sub(const int &a, const int &b) {
    int p = a - b;
    if (p < 0) p += md;
    return p;
  }
  inline int __mul(const int &a, const int &b) { return 1ll * a * b % md; }
  inline int mul(const int &a, const int &b) {
    int p = __mul(a, b);
    if (p < 0) p += md;
    return p;
  }
  template <typename T>
  int qpow(int a, T b) {
    int ret = 1;
    for (; b; b >>= 1, a = mul(a, a))
      if (b & 1) ret = mul(ret, a);
    return ret;
  }
  inline int inv(int x) { return qpow(x, md - 2); }
  inline void inv(int *F, int len, int *G = NULL, bool flg = false) {
    if (G == NULL) G = F;
    if (flg) {
      F[0] = G[0] = 1;
      for (int i = 1; i <= len; ++i) F[i] = __mul(F[i - 1], i);
    }
    std::vector<int> S(len + 1), iS(len + 1);
    S[0] = 1;
    for (int i = 1; i <= len; ++i) S[i] = mul(S[i - 1], F[i]);
    iS[len] = inv(S[len]);
    for (int i = len; i >= 1; --i) {
      iS[i - 1] = mul(iS[i], F[i]);
      G[i] = mul(S[i - 1], iS[i]);
    }
  }
  }  // namespace Mod
  using namespace Mod;
  namespace gvihvo {
  const int N = 100010;
  struct FHQ_Treap {
    int fa, son[2];
    int val, siz, key;
  };
  int cnt;
  int c, rt[N], irt[N];
  FHQ_Treap t[N];
  int new_node(int v) {
    t[++cnt].val = v;
    t[cnt].siz = 1;
    t[cnt].key = rand();
    return cnt;
  }
  void pushup(int x) {
    t[x].siz = t[t[x].son[0]].siz + t[t[x].son[1]].siz + 1;
    if (t[x].son[0]) t[t[x].son[0]].fa = x;
    if (t[x].son[1]) t[t[x].son[1]].fa = x;
    t[x].fa = 0;
  }
  pii split(int x, int k) {
    if (!x) return {0, 0};
    if (t[t[x].son[0]].siz >= k) {
      pii ret = split(t[x].son[0], k);
      t[x].son[0] = ret[1];
      pushup(x);
      return {ret[0], x};
    } else {
      pii ret = split(t[x].son[1], k - t[t[x].son[0]].siz - 1);
      t[x].son[1] = ret[0];
      pushup(x);
      return {x, ret[1]};
    }
  }
  int Merge(int x, int y) {
    if (!x || !y) return x | y;
    if (t[x].key > t[y].key) {
      t[x].son[1] = Merge(t[x].son[1], y);
      pushup(x);
      return x;
    } else {
      t[y].son[0] = Merge(x, t[y].son[0]);
      pushup(y);
      return y;
    }
  }
  void Insert(int x, int v) {
    rt[x] = Merge(rt[x], new_node(v));
    irt[rt[x]] = x;
  }
  int kth(int x, int k) {
    pii tmp1 = split(x, k - 1);
    pii tmp2 = split(tmp1[1], 1);
    int ret = t[tmp2[0]].val;
    Merge(tmp1[0], Merge(tmp2[0], tmp2[1]));
    return ret;
  }
  int Find_Root(int x) {
    while (t[x].fa) x = t[x].fa;
    return x;
  }
  int rank(int x) {
    int ret = t[t[x].son[0]].siz + 1;
    while (t[x].fa) {
      int y = t[x].fa;
      if (x == t[y].son[1]) ret += t[t[y].son[0]].siz + 1;
      x = y;
    }
    return ret;
  }
  void print(int x) {
    if (t[x].son[0]) print(t[x].son[0]);
    out(t[x].val);
    if (t[x].son[1]) print(t[x].son[1]);
  }
  int n, q;
  int p[N];
  bool vis[N];
  int pos[N];
  void main() {
    in(n, q);
    in(p + 1, p + n + 1);
    for (int i = (1); i <= (n); ++i) {
      if (vis[p[i]]) continue;
      int x = p[i], now = p[p[i]];
      vis[x] = true;
      rt[++c] = new_node(x);
      irt[rt[c]] = c;
      pos[x] = cnt;
      while (now != x) {
        Insert(c, now);
        pos[now] = cnt;
        vis[now] = true;
        now = p[now];
      }
    }
    for (int i = (1); i <= (q); ++i) {
      int op, x, y;
      in(op, x, y);
      if (op == 1) {
        int rx = Find_Root(pos[p[x]]), ry = Find_Root(pos[p[y]]);
        if (rx == ry) {
          int kx = rank(pos[p[x]]), ky = rank(pos[p[y]]);
          if (kx > ky) {
            swap(x, y);
            swap(kx, ky);
          }
          pii tmp = split(rx, kx);
          pii tmp2 = split(tmp[1], ky - kx);
          int r = irt[rx];
          rt[r] = Merge(tmp[0], tmp2[1]);
          irt[rt[r]] = r;
          rt[++c] = tmp2[0];
          irt[rt[c]] = c;
        } else {
          int kx = rank(pos[p[x]]), ky = rank(pos[p[y]]);
          pii tmp1 = split(rx, kx);
          pii tmp2 = split(ry, ky);
          int r = irt[rx];
          rt[r] = Merge(Merge(tmp1[0], tmp2[1]), Merge(tmp2[0], tmp1[1]));
          irt[rt[r]] = r;
        }
        swap(pos[p[x]], pos[p[y]]);
        swap(t[pos[p[x]]].val, t[pos[p[y]]].val);
        swap(p[x], p[y]);
      } else {
        int tmp = Find_Root(pos[x]);
        y += rank(pos[x]);
        y %= t[tmp].siz;
        if (!y) y += t[tmp].siz;
        out(kth(tmp, y));
      }
    }
  }
  void init() { ; }
  }  // namespace gvihvo
  int main() {
    gvihvo::init();
    gvihvo::main();
    return 0;
  }
  