#include <bits/stdc++.h>
long long dx[8] = {0, 1, 0, -1, 1, 1, -1, -1};
long long dy[8] = {1, 0, -1, 0, -1, 1, 1, -1};
using namespace std;
class pa3 {
 public:
  long long x;
  long long y, z;
  pa3(long long x = 0, long long y = 0, long long z = 0) : x(x), y(y), z(z) {}
  bool operator<(const pa3 &p) const {
    if (x != p.x) return x < p.x;
    if (y != p.y) return y < p.y;
    return z < p.z;
  }
  bool operator>(const pa3 &p) const {
    if (x != p.x) return x > p.x;
    if (y != p.y) return y > p.y;
    return z > p.z;
  }
  bool operator==(const pa3 &p) const {
    return x == p.x && y == p.y && z == p.z;
  }
  bool operator!=(const pa3 &p) const {
    return !(x == p.x && y == p.y && z == p.z);
  }
};
class pa4 {
 public:
  long long x;
  long long y, z, w;
  pa4(long long x = 0, long long y = 0, long long z = 0, long long w = 0)
      : x(x), y(y), z(z), w(w) {}
  bool operator<(const pa4 &p) const {
    if (x != p.x) return x < p.x;
    if (y != p.y) return y < p.y;
    if (z != p.z) return z < p.z;
    return w < p.w;
  }
  bool operator>(const pa4 &p) const {
    if (x != p.x) return x > p.x;
    if (y != p.y) return y > p.y;
    if (z != p.z) return z > p.z;
    return w > p.w;
  }
  bool operator==(const pa4 &p) const {
    return x == p.x && y == p.y && z == p.z && w == p.w;
  }
};
class pa2 {
 public:
  long long x, y;
  pa2(long long x = 0, long long y = 0) : x(x), y(y) {}
  pa2 operator+(pa2 p) { return pa2(x + p.x, y + p.y); }
  pa2 operator-(pa2 p) { return pa2(x - p.x, y - p.y); }
  bool operator<(const pa2 &p) const { return y != p.y ? y < p.y : x < p.x; }
  bool operator>(const pa2 &p) const { return x != p.x ? x < p.x : y < p.y; }
  bool operator==(const pa2 &p) const {
    return abs(x - p.x) == 0 && abs(y - p.y) == 0;
  }
  bool operator!=(const pa2 &p) const {
    return !(abs(x - p.x) == 0 && abs(y - p.y) == 0);
  }
};
string itos(long long i) {
  ostringstream s;
  s << i;
  return s.str();
}
long long Gcd(long long v, long long b) {
  if (v == 0) return b;
  if (b == 0) return v;
  if (v > b) return Gcd(b, v);
  if (v == b) return b;
  if (b % v == 0) return v;
  return Gcd(v, b % v);
}
long long mod;
long long extgcd(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long d = extgcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}
pair<long long, long long> operator+(const pair<long long, long long> &l,
                                     const pair<long long, long long> &r) {
  return {l.first + r.first, l.second + r.second};
}
pair<long long, long long> operator-(const pair<long long, long long> &l,
                                     const pair<long long, long long> &r) {
  return {l.first - r.first, l.second - r.second};
}
long long beki(long long wa, long long rr, long long warukazu) {
  if (rr == 0) return 1 % warukazu;
  if (rr == 1) return wa % warukazu;
  wa %= warukazu;
  if (rr % 2 == 1)
    return ((long long)beki(wa, rr - 1, warukazu) * (long long)wa) % warukazu;
  long long zx = beki(wa, rr / 2, warukazu);
  return (zx * zx) % warukazu;
}
long long pr[10];
long long inv[10];
long long comb(long long nn, long long rr) {
  if (rr < 0 || rr > nn || nn < 0) return 0;
  long long r = pr[nn] * inv[rr];
  r %= mod;
  r *= inv[nn - rr];
  r %= mod;
  return r;
}
void gya(long long ert) {
  pr[0] = 1;
  for (long long i = 1; i <= ert; i++) {
    pr[i] = ((long long)pr[i - 1] * i) % mod;
  }
  inv[ert] = beki(pr[ert], mod - 2, mod);
  for (long long i = ert - 1; i >= 0; i--) {
    inv[i] = (long long)inv[i + 1] * (i + 1) % mod;
  }
}
struct Segmin {
 private:
 public:
  long long cor = (1 << 19);
  vector<pair<long long, long long> > vec;
  void shoki1() {
    vec.resize(2 * cor + 3, make_pair(-(1ll << 31), 0));
    for (long long i = cor; i < 2 * cor; i++) vec[i].second = i - cor;
  }
  void shoki2() {
    for (long long i = cor - 1; i > 0; i--) {
      if (vec[2 * i].first <= vec[2 * i + 1].first)
        vec[i] = vec[2 * i];
      else
        vec[i] = vec[2 * i + 1];
    }
  }
  void updadd(long long x, long long w) {
    x += cor;
    vec[x].first += w;
    x /= 2;
    while (x) {
      if (vec[2 * x].first <= vec[2 * x + 1].first)
        vec[x] = vec[2 * x];
      else
        vec[x] = vec[2 * x + 1];
      x /= 2;
    }
  }
  void updchan(long long x, long long w) {
    x += cor;
    vec[x].first = w;
    x /= 2;
    while (x) {
      if (vec[2 * x].first <= vec[2 * x + 1].first)
        vec[x] = vec[2 * x];
      else
        vec[x] = vec[2 * x + 1];
      x /= 2;
    }
  }
  pair<long long, long long> segmin(long long a, long long b) {
    a += cor;
    b += cor;
    pair<long long, long long> ans = make_pair((1ll << 31) - 1, -1);
    while (a < b) {
      if (a & 1) {
        ans = min(ans, vec[a]);
        a++;
      }
      if (b & 1) {
        b--;
        ans = min(ans, vec[b]);
      }
      a /= 2;
      b /= 2;
    }
    return ans;
  }
  long long lower_bound(long long p, long long x) {
    p += cor;
    while (1) {
      while (!(p & 1)) p /= 2;
      if (vec[p].first <= x) break;
      p++;
      if (p == (p & (-p))) return cor;
    }
    while (1) {
      if (p >= cor) return p - cor;
      p *= 2;
      if (vec[p].first > x) {
        p++;
      }
    }
  }
};
vector<long long> G[200020];
long long p[200020];
long long d[200020];
long long id[200020];
long long dp[30][200020];
void dfs(long long r, long long di) {
  d[r] = di;
  for (auto v : G[r]) dfs(v, di + 1);
}
long long lca(long long a, long long b) {
  if (d[a] < d[b]) swap(a, b);
  long long sa = d[a] - d[b];
  for (long long i = 0; i < 19; i++)
    if (sa & (1 << i)) a = dp[i][a];
  if (a == b) return a;
  for (long long i = 18; i >= 0; i--)
    if (dp[i][a] != dp[i][b]) a = dp[i][a], b = dp[i][b];
  return dp[0][a];
}
Segmin sm;
long long vis[200020] = {};
long long dis(long long a, long long b) {
  if (a == b) return 0;
  long long p = d[a] + d[b];
  a = vis[a], b = vis[b];
  if (a > b) swap(a, b);
  return p - 2 * sm.segmin(a, b + 1).first;
  return d[a] + d[b] - 2 * d[lca(a, b)];
}
vector<long long> oi;
void dfs_oi(long long r) {
  for (auto v : G[r]) {
    oi.push_back(r);
    dfs_oi(v);
  }
  oi.push_back(r);
}
struct hoge {
  long long l;
  long long r;
  long long len;
};
struct seg {
 private:
 public:
  long long cor = (1 << 18);
  vector<hoge> vec;
  hoge mer(hoge a, hoge b) {
    if (a.l == -1 || b.l == -1) return {-1, -1, -1};
    long long pl = -1, pr = -1, tmp = -1;
    long long la = a.len;
    if (tmp < la) pl = a.l, pr = a.r, tmp = la;
    long long lb = b.len;
    if (tmp < lb) pl = b.l, pr = b.r, tmp = lb;
    long long d1 = dis(a.l, b.l);
    if (tmp < d1) pl = a.l, pr = b.l, tmp = d1;
    long long d2 = dis(a.l, b.r);
    if (tmp < d2) pl = a.l, pr = b.r, tmp = d2;
    if (!(d1 + d2 == lb || abs(d1 - d2) == lb)) return {-1, -1, -1};
    long long d3 = dis(a.r, b.l);
    if (tmp < d3) pl = a.r, pr = b.l, tmp = d3;
    long long d4 = dis(a.r, b.r);
    if (tmp < d4) pl = a.r, pr = b.r, tmp = d4;
    if (!(d3 + d4 == lb || abs(d3 - d4) == lb)) return {-1, -1, -1};
    if (!(d3 + d1 == la || abs(d3 - d1) == la)) return {-1, -1, -1};
    if (!(d4 + d2 == la || abs(d4 - d2) == la)) return {-1, -1, -1};
    return {pl, pr, tmp};
  }
  void shoki1() { vec.resize(2 * cor + 3, (hoge){-1, -1, -1}); }
  void shoki2() {
    for (long long i = cor - 1; i > 0; i--)
      vec[i] = mer(vec[2 * i], vec[2 * i + 1]);
  }
  void updchan(long long x) {
    x += cor;
    vec[x] = {p[x - cor], p[x - cor]};
    while (x) {
      x /= 2;
      vec[x] = mer(vec[2 * x], vec[2 * x + 1]);
    }
  }
  long long lower_bound(long long pi = 0) {
    pi += cor;
    hoge ima = {p[0], p[0]};
    while (1) {
      while (!(pi & 1)) pi /= 2;
      hoge tmp = mer(ima, vec[pi]);
      if (tmp.l == -1) break;
      ima = tmp;
      pi++;
      if (pi == (pi & (-pi))) return cor;
    }
    while (1) {
      if (pi >= cor) return pi - cor;
      pi *= 2;
      hoge tmp = mer(ima, vec[pi]);
      if (tmp.l >= 0) {
        ima = tmp;
        pi++;
      }
    }
  }
};
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  long long n;
  cin >> n;
  for (long long i = 1; i <= n; i++) {
    long long y;
    cin >> y;
    id[i] = y;
    p[y] = i;
  }
  dp[0][1] = 1;
  for (long long i = 2; i <= n; i++) {
    long long y;
    cin >> y;
    G[y].push_back(i);
    dp[0][i] = y;
  }
  dfs(1, 0);
  seg ss;
  ss.shoki1();
  sm.shoki1();
  dfs_oi(1);
  for (long long i = 0; i <= n; i++) vis[i] = -1;
  for (long long i = 0; i < oi.size(); i++) {
    if (vis[oi[i]] == -1) {
      vis[oi[i]] = i;
    }
    sm.vec[sm.cor + i].first = d[oi[i]];
  }
  sm.shoki2();
  for (long long i = 0; i < n; i++) {
    ss.vec[ss.cor + i] = {p[i], p[i], 0};
  }
  ss.shoki2();
  long long q;
  cin >> q;
  for (long long er = 0; er < q; er++) {
    long long t;
    cin >> t;
    if (t == 1) {
      long long y, yy;
      cin >> y >> yy;
      swap(id[y], id[yy]);
      swap(p[id[y]], p[id[yy]]);
      ss.updchan(id[y]);
      ss.updchan(id[yy]);
    } else {
      cout << ss.lower_bound() << endl;
    }
  }
  return 0;
}

### Prompt

Develop a solution in CPP to the problem described below:

Once Grisha found a tree (connected graph without cycles) with a root in node 1.

But this tree was not just a tree. A permutation p of integers from 0 to n - 1 is written in nodes, a number p_i is written in node i.

As Grisha likes to invent some strange and interesting problems for himself, but not always can solve them, you need to help him deal with two types of queries on this tree.

Let's define a function MEX(S), where S is a set of non-negative integers, as a smallest non-negative integer that is not included in this set.

Let l be a simple path in this tree. So let's define indices of nodes which lie on l as u_1, u_2, …, u_k. 

Define V(l) as a set {p_{u_1}, p_{u_2}, … , p_{u_k}}. 

Then queries are: 

  1. For two nodes i and j, swap p_i and p_j. 
  2. Find the maximum value of MEX(V(l)) in all possible l. 

Input

The first line contains a single integer n (2 ≤ n ≤ 2 ⋅ 10^5) — the number of nodes of a tree.

The second line contains n integers — p_1, p_2, …, p_n (0≤ p_i < n) — the permutation p, it's guaranteed that all numbers are different .

The third line contains n - 1 integers — d_2, d_3, …, d_n (1 ≤ d_i < i), where d_i is a direct ancestor of node i in a tree.

The fourth line contains a single integer q (1 ≤ q ≤ 2 ⋅ 10^5) — the number of queries.

The following q lines contain the description of queries:

At the beginning of each of next q lines, there is a single integer t (1 or 2) — the type of a query: 

  1. If t = 1, the line also contains two integers i and j (1 ≤ i, j ≤ n) — the indices of nodes, where values of the permutation should be swapped. 
  2. If t = 2, you need to find the maximum value of MEX(V(l)) in all possible l. 

Output

For each type 2 query print a single integer — the answer for this query.

Examples

Input


6
2 5 0 3 1 4
1 1 3 3 3
3
2
1 6 3
2


Output


3
2


Input


6
5 2 1 4 3 0
1 1 1 3 3
9
2
1 5 3
2
1 6 1
2
1 4 2
2
1 1 6
2


Output


3
2
4
4
2

Note

Number written in brackets is a permutation value of a node. 

<image> In the first example, for the first query, optimal path is a path from node 1 to node 5. For it, set of values is \{0, 1, 2\} and MEX is 3.  <image> For the third query, optimal path is a path from node 5 to node 6. For it, set of values is \{0, 1, 4\} and MEX is 2.  <image> In the second example, for the first query, optimal path is a path from node 2 to node 6. For it, set of values is \{0, 1, 2, 5\} and MEX is 3.  <image> For the third query, optimal path is a path from node 5 to node 6. For it, set of values is \{0, 1, 3\} and MEX is 2.  <image> For the fifth query, optimal path is a path from node 5 to node 2. For it, set of values is \{0, 1, 2, 3\} and MEX is 4.  <image> For the seventh query, optimal path is a path from node 5 to node 4. For it, set of values is \{0, 1, 2, 3\} and MEX is 4.  <image> For the ninth query, optimal path is a path from node 6 to node 5. For it, set of values is \{0, 1, 3\} and MEX is 2. 

### Response

```cpp
#include <bits/stdc++.h>
long long dx[8] = {0, 1, 0, -1, 1, 1, -1, -1};
long long dy[8] = {1, 0, -1, 0, -1, 1, 1, -1};
using namespace std;
class pa3 {
 public:
  long long x;
  long long y, z;
  pa3(long long x = 0, long long y = 0, long long z = 0) : x(x), y(y), z(z) {}
  bool operator<(const pa3 &p) const {
    if (x != p.x) return x < p.x;
    if (y != p.y) return y < p.y;
    return z < p.z;
  }
  bool operator>(const pa3 &p) const {
    if (x != p.x) return x > p.x;
    if (y != p.y) return y > p.y;
    return z > p.z;
  }
  bool operator==(const pa3 &p) const {
    return x == p.x && y == p.y && z == p.z;
  }
  bool operator!=(const pa3 &p) const {
    return !(x == p.x && y == p.y && z == p.z);
  }
};
class pa4 {
 public:
  long long x;
  long long y, z, w;
  pa4(long long x = 0, long long y = 0, long long z = 0, long long w = 0)
      : x(x), y(y), z(z), w(w) {}
  bool operator<(const pa4 &p) const {
    if (x != p.x) return x < p.x;
    if (y != p.y) return y < p.y;
    if (z != p.z) return z < p.z;
    return w < p.w;
  }
  bool operator>(const pa4 &p) const {
    if (x != p.x) return x > p.x;
    if (y != p.y) return y > p.y;
    if (z != p.z) return z > p.z;
    return w > p.w;
  }
  bool operator==(const pa4 &p) const {
    return x == p.x && y == p.y && z == p.z && w == p.w;
  }
};
class pa2 {
 public:
  long long x, y;
  pa2(long long x = 0, long long y = 0) : x(x), y(y) {}
  pa2 operator+(pa2 p) { return pa2(x + p.x, y + p.y); }
  pa2 operator-(pa2 p) { return pa2(x - p.x, y - p.y); }
  bool operator<(const pa2 &p) const { return y != p.y ? y < p.y : x < p.x; }
  bool operator>(const pa2 &p) const { return x != p.x ? x < p.x : y < p.y; }
  bool operator==(const pa2 &p) const {
    return abs(x - p.x) == 0 && abs(y - p.y) == 0;
  }
  bool operator!=(const pa2 &p) const {
    return !(abs(x - p.x) == 0 && abs(y - p.y) == 0);
  }
};
string itos(long long i) {
  ostringstream s;
  s << i;
  return s.str();
}
long long Gcd(long long v, long long b) {
  if (v == 0) return b;
  if (b == 0) return v;
  if (v > b) return Gcd(b, v);
  if (v == b) return b;
  if (b % v == 0) return v;
  return Gcd(v, b % v);
}
long long mod;
long long extgcd(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long d = extgcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}
pair<long long, long long> operator+(const pair<long long, long long> &l,
                                     const pair<long long, long long> &r) {
  return {l.first + r.first, l.second + r.second};
}
pair<long long, long long> operator-(const pair<long long, long long> &l,
                                     const pair<long long, long long> &r) {
  return {l.first - r.first, l.second - r.second};
}
long long beki(long long wa, long long rr, long long warukazu) {
  if (rr == 0) return 1 % warukazu;
  if (rr == 1) return wa % warukazu;
  wa %= warukazu;
  if (rr % 2 == 1)
    return ((long long)beki(wa, rr - 1, warukazu) * (long long)wa) % warukazu;
  long long zx = beki(wa, rr / 2, warukazu);
  return (zx * zx) % warukazu;
}
long long pr[10];
long long inv[10];
long long comb(long long nn, long long rr) {
  if (rr < 0 || rr > nn || nn < 0) return 0;
  long long r = pr[nn] * inv[rr];
  r %= mod;
  r *= inv[nn - rr];
  r %= mod;
  return r;
}
void gya(long long ert) {
  pr[0] = 1;
  for (long long i = 1; i <= ert; i++) {
    pr[i] = ((long long)pr[i - 1] * i) % mod;
  }
  inv[ert] = beki(pr[ert], mod - 2, mod);
  for (long long i = ert - 1; i >= 0; i--) {
    inv[i] = (long long)inv[i + 1] * (i + 1) % mod;
  }
}
struct Segmin {
 private:
 public:
  long long cor = (1 << 19);
  vector<pair<long long, long long> > vec;
  void shoki1() {
    vec.resize(2 * cor + 3, make_pair(-(1ll << 31), 0));
    for (long long i = cor; i < 2 * cor; i++) vec[i].second = i - cor;
  }
  void shoki2() {
    for (long long i = cor - 1; i > 0; i--) {
      if (vec[2 * i].first <= vec[2 * i + 1].first)
        vec[i] = vec[2 * i];
      else
        vec[i] = vec[2 * i + 1];
    }
  }
  void updadd(long long x, long long w) {
    x += cor;
    vec[x].first += w;
    x /= 2;
    while (x) {
      if (vec[2 * x].first <= vec[2 * x + 1].first)
        vec[x] = vec[2 * x];
      else
        vec[x] = vec[2 * x + 1];
      x /= 2;
    }
  }
  void updchan(long long x, long long w) {
    x += cor;
    vec[x].first = w;
    x /= 2;
    while (x) {
      if (vec[2 * x].first <= vec[2 * x + 1].first)
        vec[x] = vec[2 * x];
      else
        vec[x] = vec[2 * x + 1];
      x /= 2;
    }
  }
  pair<long long, long long> segmin(long long a, long long b) {
    a += cor;
    b += cor;
    pair<long long, long long> ans = make_pair((1ll << 31) - 1, -1);
    while (a < b) {
      if (a & 1) {
        ans = min(ans, vec[a]);
        a++;
      }
      if (b & 1) {
        b--;
        ans = min(ans, vec[b]);
      }
      a /= 2;
      b /= 2;
    }
    return ans;
  }
  long long lower_bound(long long p, long long x) {
    p += cor;
    while (1) {
      while (!(p & 1)) p /= 2;
      if (vec[p].first <= x) break;
      p++;
      if (p == (p & (-p))) return cor;
    }
    while (1) {
      if (p >= cor) return p - cor;
      p *= 2;
      if (vec[p].first > x) {
        p++;
      }
    }
  }
};
vector<long long> G[200020];
long long p[200020];
long long d[200020];
long long id[200020];
long long dp[30][200020];
void dfs(long long r, long long di) {
  d[r] = di;
  for (auto v : G[r]) dfs(v, di + 1);
}
long long lca(long long a, long long b) {
  if (d[a] < d[b]) swap(a, b);
  long long sa = d[a] - d[b];
  for (long long i = 0; i < 19; i++)
    if (sa & (1 << i)) a = dp[i][a];
  if (a == b) return a;
  for (long long i = 18; i >= 0; i--)
    if (dp[i][a] != dp[i][b]) a = dp[i][a], b = dp[i][b];
  return dp[0][a];
}
Segmin sm;
long long vis[200020] = {};
long long dis(long long a, long long b) {
  if (a == b) return 0;
  long long p = d[a] + d[b];
  a = vis[a], b = vis[b];
  if (a > b) swap(a, b);
  return p - 2 * sm.segmin(a, b + 1).first;
  return d[a] + d[b] - 2 * d[lca(a, b)];
}
vector<long long> oi;
void dfs_oi(long long r) {
  for (auto v : G[r]) {
    oi.push_back(r);
    dfs_oi(v);
  }
  oi.push_back(r);
}
struct hoge {
  long long l;
  long long r;
  long long len;
};
struct seg {
 private:
 public:
  long long cor = (1 << 18);
  vector<hoge> vec;
  hoge mer(hoge a, hoge b) {
    if (a.l == -1 || b.l == -1) return {-1, -1, -1};
    long long pl = -1, pr = -1, tmp = -1;
    long long la = a.len;
    if (tmp < la) pl = a.l, pr = a.r, tmp = la;
    long long lb = b.len;
    if (tmp < lb) pl = b.l, pr = b.r, tmp = lb;
    long long d1 = dis(a.l, b.l);
    if (tmp < d1) pl = a.l, pr = b.l, tmp = d1;
    long long d2 = dis(a.l, b.r);
    if (tmp < d2) pl = a.l, pr = b.r, tmp = d2;
    if (!(d1 + d2 == lb || abs(d1 - d2) == lb)) return {-1, -1, -1};
    long long d3 = dis(a.r, b.l);
    if (tmp < d3) pl = a.r, pr = b.l, tmp = d3;
    long long d4 = dis(a.r, b.r);
    if (tmp < d4) pl = a.r, pr = b.r, tmp = d4;
    if (!(d3 + d4 == lb || abs(d3 - d4) == lb)) return {-1, -1, -1};
    if (!(d3 + d1 == la || abs(d3 - d1) == la)) return {-1, -1, -1};
    if (!(d4 + d2 == la || abs(d4 - d2) == la)) return {-1, -1, -1};
    return {pl, pr, tmp};
  }
  void shoki1() { vec.resize(2 * cor + 3, (hoge){-1, -1, -1}); }
  void shoki2() {
    for (long long i = cor - 1; i > 0; i--)
      vec[i] = mer(vec[2 * i], vec[2 * i + 1]);
  }
  void updchan(long long x) {
    x += cor;
    vec[x] = {p[x - cor], p[x - cor]};
    while (x) {
      x /= 2;
      vec[x] = mer(vec[2 * x], vec[2 * x + 1]);
    }
  }
  long long lower_bound(long long pi = 0) {
    pi += cor;
    hoge ima = {p[0], p[0]};
    while (1) {
      while (!(pi & 1)) pi /= 2;
      hoge tmp = mer(ima, vec[pi]);
      if (tmp.l == -1) break;
      ima = tmp;
      pi++;
      if (pi == (pi & (-pi))) return cor;
    }
    while (1) {
      if (pi >= cor) return pi - cor;
      pi *= 2;
      hoge tmp = mer(ima, vec[pi]);
      if (tmp.l >= 0) {
        ima = tmp;
        pi++;
      }
    }
  }
};
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  long long n;
  cin >> n;
  for (long long i = 1; i <= n; i++) {
    long long y;
    cin >> y;
    id[i] = y;
    p[y] = i;
  }
  dp[0][1] = 1;
  for (long long i = 2; i <= n; i++) {
    long long y;
    cin >> y;
    G[y].push_back(i);
    dp[0][i] = y;
  }
  dfs(1, 0);
  seg ss;
  ss.shoki1();
  sm.shoki1();
  dfs_oi(1);
  for (long long i = 0; i <= n; i++) vis[i] = -1;
  for (long long i = 0; i < oi.size(); i++) {
    if (vis[oi[i]] == -1) {
      vis[oi[i]] = i;
    }
    sm.vec[sm.cor + i].first = d[oi[i]];
  }
  sm.shoki2();
  for (long long i = 0; i < n; i++) {
    ss.vec[ss.cor + i] = {p[i], p[i], 0};
  }
  ss.shoki2();
  long long q;
  cin >> q;
  for (long long er = 0; er < q; er++) {
    long long t;
    cin >> t;
    if (t == 1) {
      long long y, yy;
      cin >> y >> yy;
      swap(id[y], id[yy]);
      swap(p[id[y]], p[id[yy]]);
      ss.updchan(id[y]);
      ss.updchan(id[yy]);
    } else {
      cout << ss.lower_bound() << endl;
    }
  }
  return 0;
}

```