#include <bits/stdc++.h>
#pragma GGC optimize("Ofast")
using namespace std;
template <typename T>
void dprintln(const T &t) {
  cout << t << endl;
}
template <typename T, typename... Args>
void dprintln(const T &t, const Args &...rest) {
  cout << t << ' ';
  dprintln(rest...);
}
template <typename T>
void println(const T &t) {
  cout << t << '\n';
}
template <typename T, typename... Args>
void println(const T &t, const Args &...rest) {
  cout << t << ' ';
  println(rest...);
}
template <typename T>
void print(const T &t) {
  cout << t << ' ';
}
template <typename T, typename... Args>
void print(const T &t, const Args &...rest) {
  cout << t;
  print(rest...);
}
template <class T>
void scan(T &t) {
  cin >> t;
}
template <class T, class... Args>
void scan(T &a, Args &...rest) {
  cin >> a;
  scan(rest...);
}
using ll = long long;
using vl = vector<ll>;
using vi = vector<int>;
using pii = pair<int, int>;
using vb = vector<bool>;
using vpii = vector<pii>;
template <typename T>
struct bit {
  vector<T> a;
  explicit bit(int n, int v = 0) {
    a.resize(n + 1);
    if (v != 0) {
      for (int i = 1; i <= n; ++i) a[i] = v;
    }
  }
  T sum(T x) {
    T res = 0;
    while (x) {
      res += a[x];
      x -= x & -x;
    }
    return res;
  }
  T sum(int l, int r) {
    if (l > r) return 0;
    return sum(r) - sum(l - 1);
  }
  void add(int x, T v) {
    while (x < a.size()) {
      a[x] += v;
      x += x & -x;
    }
  }
  void clear() { fill(a.begin(), a.end(), 0); }
};
vi get_prime(int n) {
  vi minp(n + 1), p;
  for (int i = 2; i <= n; i++) {
    if (!minp[i]) {
      minp[i] = i;
      p.push_back(i);
    }
    for (auto &x : p) {
      if (x <= minp[i] && x * i <= n)
        minp[x * i] = x;
      else
        break;
    }
  }
  return p;
}
const int mod = 1000000007;
inline void add_mod(ll &x, const ll &y) {
  x += y;
  if (x >= mod) x -= mod;
}
void sub_mod(ll &x, const ll &y) {
  x -= y;
  if (x < 0) x += mod;
}
template <typename T>
using vv = vector<vector<T>>;
template <typename T1, typename T2 = T1>
using vp = vector<pair<T1, T2>>;
template <typename T, int n>
using va = vector<array<T, n>>;
using vec = vector<ll>;
using mat = vector<vec>;
mat get_I(int n) {
  mat res(n, vec(n));
  for (int i = 0; i < n; i++) res[i][i] = 1;
  return res;
}
mat operator*(const mat &a, const mat &b) {
  mat c(a.size(), vec(b[0].size()));
  for (size_t i = 0; i < a.size(); i++) {
    for (size_t j = 0; j < a[0].size(); j++) {
      if (a[i][j]) {
        for (size_t k = 0; k < b[0].size(); k++) {
          add_mod(c[i][k], a[i][j] * b[j][k] % mod);
        }
      }
    }
  }
  return c;
}
vec operator*(const mat &a, const vec &b) {
  vec c(a.size());
  for (size_t i = 0; i < a.size(); i++) {
    for (size_t j = 0; j < a[0].size(); j++) {
      add_mod(c[i], a[i][j] * b[j] % mod);
    }
  }
  return c;
}
mat pow(mat a, ll n) {
  mat res(a.size(), vec(a[0].size()));
  for (size_t i = 0; i < a.size(); i++) {
    res[i][i] = 1;
  }
  while (n) {
    if (n & 1) {
      res = res * a;
    }
    a = a * a;
    n >>= 1;
  }
  return res;
}
struct UF {
  vi par;
  explicit UF(int n) {
    par.assign(n + 1, 0);
    for (int i = (1); i < (n + 1); ++i) par[i] = i;
  }
  int find(int x) { return x == par[x] ? x : par[x] = find(par[x]); }
  void unite(int x, int y) { par[find(x)] = find(y); }
};
vi get_popcnt(int n) {
  vi res(n + 1);
  for (int i = (0); i < (n); ++i) {
    if (i * 2 <= n) res[i * 2] = res[i];
    if ((i & 1) == 0) res[i + 1] = res[i] + 1;
  }
  return res;
}
const int N = (int)2e5 + 5, M = 1005;
int head[N], tail;
struct edge {
  int to, next;
} E[N];
inline void add_edge(int u, int v) {
  E[++tail] = {v, head[u]};
  head[u] = tail;
}
int fa[N][18];
int dep[N];
int lca(int u, int v) {
  if (dep[u] < dep[v]) swap(u, v);
  int dif = dep[u] - dep[v];
  for (int i = (0); i < (18); ++i) {
    if (dif & 1 << i) {
      u = fa[u][i];
    }
  }
  if (u == v) return u;
  for (int i = (17); i >= (0); i--) {
    if (fa[u][i] != fa[v][i]) {
      u = fa[u][i];
      v = fa[v][i];
    }
  }
  return fa[u][0];
}
vi check(int a, int b, int c, int d) {
  if (a == 0) return {c, d};
  int x[4] = {a, b, c, d};
  for (int i = (0); i < (3); ++i)
    for (int j = (i + 1); j < (4); ++j) {
      int u = lca(x[i], x[j]);
      bool flag = true;
      for (int k = (0); k < (4); ++k) {
        if (k != i && k != j) {
          int t = x[k];
          if (dep[t] >= dep[u] && (lca(t, x[i]) == t || lca(t, x[j]) == t)) {
            continue;
          } else {
            flag = false;
            break;
          }
        }
      }
      if (flag) return {x[i], x[j]};
    }
  return {-1, -1};
}
struct node {
  bool ok;
  int u, v;
} tree[N * 4];
int leaf[N];
int p[N];
int v[N];
void push_up(int id) {
  auto &f = tree[id], lson = tree[id * 2], rson = tree[id * 2 + 1];
  if (lson.ok && rson.ok) {
    auto res = check(lson.u, lson.v, rson.u, rson.v);
    if (res[0] != -1) {
      f.ok = true;
      f.u = res[0];
      f.v = res[1];
    } else
      f.ok = false;
  } else {
    f.ok = false;
  }
}
void build(int id, int l, int r) {
  if (l == r) {
    leaf[l] = id;
    tree[id].u = tree[id].v = v[l];
    tree[id].ok = true;
    return;
  }
  int mid = (l + r) / 2;
  build(id * 2, l, mid);
  build(id * 2 + 1, mid + 1, r);
  push_up(id);
}
void work(int i) {
  int id = leaf[p[i]];
  tree[id].u = tree[id].v = i;
  while (id != 1) {
    id /= 2;
    push_up(id);
  }
}
void upd(int i, int j) {
  swap(p[i], p[j]);
  work(i);
  work(j);
}
int query(int id, int l, int r, int u, int v) {
  if (tree[id].ok) {
    auto t = check(u, v, tree[id].u, tree[id].v);
    if (t[0] != -1) return r - l + 1;
    if (l == r) return 0;
  }
  int mid = (l + r) / 2;
  auto &lson = tree[id * 2];
  if (lson.ok) {
    auto t = check(u, v, lson.u, lson.v);
    if (t[0] != -1) {
      return mid - l + 1 + query(id * 2 + 1, mid + 1, r, t[0], t[1]);
    }
  }
  return query(id * 2, l, mid, u, v);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  for (int i = (1); i < (n + 1); ++i) cin >> p[i], v[p[i]] = i;
  for (int i = (2); i < (n + 1); ++i) {
    cin >> fa[i][0];
    dep[i] = dep[fa[i][0]] + 1;
  }
  for (int i = (1); i < (18); ++i)
    for (int j = (2); j < (n + 1); ++j) fa[j][i] = fa[fa[j][i - 1]][i - 1];
  build(1, 0, n - 1);
  int q;
  cin >> q;
  for (int _ = 0, __ = (int)q; _ < __; _++) {
    int t, i, j;
    scan(t);
    if (t == 1) {
      scan(i, j);
      upd(i, j);
    } else {
      println(query(1, 0, n - 1, 0, 0));
    }
  }
  return 0;
}

### Prompt

Create a solution in cpp for the following problem:

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>
#pragma GGC optimize("Ofast")
using namespace std;
template <typename T>
void dprintln(const T &t) {
  cout << t << endl;
}
template <typename T, typename... Args>
void dprintln(const T &t, const Args &...rest) {
  cout << t << ' ';
  dprintln(rest...);
}
template <typename T>
void println(const T &t) {
  cout << t << '\n';
}
template <typename T, typename... Args>
void println(const T &t, const Args &...rest) {
  cout << t << ' ';
  println(rest...);
}
template <typename T>
void print(const T &t) {
  cout << t << ' ';
}
template <typename T, typename... Args>
void print(const T &t, const Args &...rest) {
  cout << t;
  print(rest...);
}
template <class T>
void scan(T &t) {
  cin >> t;
}
template <class T, class... Args>
void scan(T &a, Args &...rest) {
  cin >> a;
  scan(rest...);
}
using ll = long long;
using vl = vector<ll>;
using vi = vector<int>;
using pii = pair<int, int>;
using vb = vector<bool>;
using vpii = vector<pii>;
template <typename T>
struct bit {
  vector<T> a;
  explicit bit(int n, int v = 0) {
    a.resize(n + 1);
    if (v != 0) {
      for (int i = 1; i <= n; ++i) a[i] = v;
    }
  }
  T sum(T x) {
    T res = 0;
    while (x) {
      res += a[x];
      x -= x & -x;
    }
    return res;
  }
  T sum(int l, int r) {
    if (l > r) return 0;
    return sum(r) - sum(l - 1);
  }
  void add(int x, T v) {
    while (x < a.size()) {
      a[x] += v;
      x += x & -x;
    }
  }
  void clear() { fill(a.begin(), a.end(), 0); }
};
vi get_prime(int n) {
  vi minp(n + 1), p;
  for (int i = 2; i <= n; i++) {
    if (!minp[i]) {
      minp[i] = i;
      p.push_back(i);
    }
    for (auto &x : p) {
      if (x <= minp[i] && x * i <= n)
        minp[x * i] = x;
      else
        break;
    }
  }
  return p;
}
const int mod = 1000000007;
inline void add_mod(ll &x, const ll &y) {
  x += y;
  if (x >= mod) x -= mod;
}
void sub_mod(ll &x, const ll &y) {
  x -= y;
  if (x < 0) x += mod;
}
template <typename T>
using vv = vector<vector<T>>;
template <typename T1, typename T2 = T1>
using vp = vector<pair<T1, T2>>;
template <typename T, int n>
using va = vector<array<T, n>>;
using vec = vector<ll>;
using mat = vector<vec>;
mat get_I(int n) {
  mat res(n, vec(n));
  for (int i = 0; i < n; i++) res[i][i] = 1;
  return res;
}
mat operator*(const mat &a, const mat &b) {
  mat c(a.size(), vec(b[0].size()));
  for (size_t i = 0; i < a.size(); i++) {
    for (size_t j = 0; j < a[0].size(); j++) {
      if (a[i][j]) {
        for (size_t k = 0; k < b[0].size(); k++) {
          add_mod(c[i][k], a[i][j] * b[j][k] % mod);
        }
      }
    }
  }
  return c;
}
vec operator*(const mat &a, const vec &b) {
  vec c(a.size());
  for (size_t i = 0; i < a.size(); i++) {
    for (size_t j = 0; j < a[0].size(); j++) {
      add_mod(c[i], a[i][j] * b[j] % mod);
    }
  }
  return c;
}
mat pow(mat a, ll n) {
  mat res(a.size(), vec(a[0].size()));
  for (size_t i = 0; i < a.size(); i++) {
    res[i][i] = 1;
  }
  while (n) {
    if (n & 1) {
      res = res * a;
    }
    a = a * a;
    n >>= 1;
  }
  return res;
}
struct UF {
  vi par;
  explicit UF(int n) {
    par.assign(n + 1, 0);
    for (int i = (1); i < (n + 1); ++i) par[i] = i;
  }
  int find(int x) { return x == par[x] ? x : par[x] = find(par[x]); }
  void unite(int x, int y) { par[find(x)] = find(y); }
};
vi get_popcnt(int n) {
  vi res(n + 1);
  for (int i = (0); i < (n); ++i) {
    if (i * 2 <= n) res[i * 2] = res[i];
    if ((i & 1) == 0) res[i + 1] = res[i] + 1;
  }
  return res;
}
const int N = (int)2e5 + 5, M = 1005;
int head[N], tail;
struct edge {
  int to, next;
} E[N];
inline void add_edge(int u, int v) {
  E[++tail] = {v, head[u]};
  head[u] = tail;
}
int fa[N][18];
int dep[N];
int lca(int u, int v) {
  if (dep[u] < dep[v]) swap(u, v);
  int dif = dep[u] - dep[v];
  for (int i = (0); i < (18); ++i) {
    if (dif & 1 << i) {
      u = fa[u][i];
    }
  }
  if (u == v) return u;
  for (int i = (17); i >= (0); i--) {
    if (fa[u][i] != fa[v][i]) {
      u = fa[u][i];
      v = fa[v][i];
    }
  }
  return fa[u][0];
}
vi check(int a, int b, int c, int d) {
  if (a == 0) return {c, d};
  int x[4] = {a, b, c, d};
  for (int i = (0); i < (3); ++i)
    for (int j = (i + 1); j < (4); ++j) {
      int u = lca(x[i], x[j]);
      bool flag = true;
      for (int k = (0); k < (4); ++k) {
        if (k != i && k != j) {
          int t = x[k];
          if (dep[t] >= dep[u] && (lca(t, x[i]) == t || lca(t, x[j]) == t)) {
            continue;
          } else {
            flag = false;
            break;
          }
        }
      }
      if (flag) return {x[i], x[j]};
    }
  return {-1, -1};
}
struct node {
  bool ok;
  int u, v;
} tree[N * 4];
int leaf[N];
int p[N];
int v[N];
void push_up(int id) {
  auto &f = tree[id], lson = tree[id * 2], rson = tree[id * 2 + 1];
  if (lson.ok && rson.ok) {
    auto res = check(lson.u, lson.v, rson.u, rson.v);
    if (res[0] != -1) {
      f.ok = true;
      f.u = res[0];
      f.v = res[1];
    } else
      f.ok = false;
  } else {
    f.ok = false;
  }
}
void build(int id, int l, int r) {
  if (l == r) {
    leaf[l] = id;
    tree[id].u = tree[id].v = v[l];
    tree[id].ok = true;
    return;
  }
  int mid = (l + r) / 2;
  build(id * 2, l, mid);
  build(id * 2 + 1, mid + 1, r);
  push_up(id);
}
void work(int i) {
  int id = leaf[p[i]];
  tree[id].u = tree[id].v = i;
  while (id != 1) {
    id /= 2;
    push_up(id);
  }
}
void upd(int i, int j) {
  swap(p[i], p[j]);
  work(i);
  work(j);
}
int query(int id, int l, int r, int u, int v) {
  if (tree[id].ok) {
    auto t = check(u, v, tree[id].u, tree[id].v);
    if (t[0] != -1) return r - l + 1;
    if (l == r) return 0;
  }
  int mid = (l + r) / 2;
  auto &lson = tree[id * 2];
  if (lson.ok) {
    auto t = check(u, v, lson.u, lson.v);
    if (t[0] != -1) {
      return mid - l + 1 + query(id * 2 + 1, mid + 1, r, t[0], t[1]);
    }
  }
  return query(id * 2, l, mid, u, v);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  for (int i = (1); i < (n + 1); ++i) cin >> p[i], v[p[i]] = i;
  for (int i = (2); i < (n + 1); ++i) {
    cin >> fa[i][0];
    dep[i] = dep[fa[i][0]] + 1;
  }
  for (int i = (1); i < (18); ++i)
    for (int j = (2); j < (n + 1); ++j) fa[j][i] = fa[fa[j][i - 1]][i - 1];
  build(1, 0, n - 1);
  int q;
  cin >> q;
  for (int _ = 0, __ = (int)q; _ < __; _++) {
    int t, i, j;
    scan(t);
    if (t == 1) {
      scan(i, j);
      upd(i, j);
    } else {
      println(query(1, 0, n - 1, 0, 0));
    }
  }
  return 0;
}

```