#include <bits/stdc++.h>
namespace __IO {
int ch;
inline int read() {
  static int x;
  while (isspace(ch = getchar()))
    ;
  x = ch & 15;
  while (isdigit(ch = getchar())) x = x * 10 + (ch & 15);
  return x;
}
}  // namespace __IO
using __IO::read;
int head[200010], cnt;
struct Edge {
  int to, nxt;
} e[200010];
inline void addedge(int a, int b) {
  e[++cnt] = (Edge){b, head[a]};
  head[a] = cnt;
}
int fa[200010], sz[200010], dep[200010];
int top[200010], dfn[200010], idx;
int find(int x) { return x == top[x] ? x : (top[x] = find(top[x])); }
void dfs(int u) {
  int son = 0;
  dfn[u] = ++idx, sz[u] = 1;
  for (int i = head[u], v; i; i = e[i].nxt) {
    v = e[i].to;
    dep[v] = dep[u] + 1;
    dfs(v), sz[u] += sz[v];
    if (sz[v] > sz[son]) son = v;
  }
  if (son) top[son] = u;
}
inline int LCA(int x, int y) {
  while (top[x] != top[y]) {
    if (dep[top[x]] > dep[top[y]])
      x = fa[top[x]];
    else
      y = fa[top[y]];
  }
  return dep[x] < dep[y] ? x : y;
}
int n, m, w[200010], ret[200010];
inline bool in_sub(int x, int y) {
  return (dfn[x] >= dfn[y]) && (dfn[x] < dfn[y] + sz[y]);
}
inline bool in_line(int x, int y, int z) {
  static int lca;
  lca = LCA(x, y);
  return in_sub(z, lca) && (in_sub(x, z) || in_sub(y, z));
}
inline bool in_line(int x, int y, int l, int r) {
  return in_line(x, y, l) && in_line(x, y, r);
}
struct node {
  bool line;
  int l, r;
  inline node() {}
  inline node(int __l) : line(true), l(__l), r(__l) {}
  inline node(int __l, int __r) : line(true), l(__l), r(__r) {}
  inline node(bool __line, int __l, int __r) : line(__line), l(__l), r(__r) {}
  static inline node NS() { return node(0, -1, -1); }
  inline node operator+(const node &rhs) const {
    if (!l || !r) return rhs;
    if (!line || !rhs.line) return NS();
    const int x = rhs.l, y = rhs.r;
    if (in_line(l, r, x, y)) return node(l, r);
    if (in_line(l, x, r, y)) return node(l, x);
    if (in_line(l, y, x, r)) return node(l, y);
    if (in_line(r, x, l, y)) return node(r, x);
    if (in_line(r, y, l, x)) return node(r, y);
    if (in_line(x, y, l, r)) return node(x, y);
    return NS();
  }
} I(0, 0, 0);
namespace SgT {
node V[200010 << 2];
void build(const int rt, const int l, const int r) {
  if (l == r) {
    V[rt] = node(ret[l]);
    return;
  }
  const int mid = l + r >> 1;
  build(rt << 1, l, mid), build(rt << 1 | 1, mid + 1, r);
  V[rt] = V[rt << 1] + V[rt << 1 | 1];
}
int pos;
void __modify(const int rt, const int l, const int r) {
  if (l == r) {
    V[rt] = node(ret[l]);
    return;
  }
  const int mid = l + r >> 1;
  if (pos <= mid)
    __modify(rt << 1, l, mid);
  else
    __modify(rt << 1 | 1, mid + 1, r);
  V[rt] = V[rt << 1] + V[rt << 1 | 1];
}
void modify(const int __pos) {
  pos = __pos;
  __modify(1, 0, n - 1);
}
node now;
int res;
void __query(int rt, int l, int r) {
  if (l == r) {
    res = l;
    return;
  }
  node tmp = now + V[rt << 1];
  const int mid = l + r >> 1;
  if (tmp.line) {
    now = tmp;
    __query(rt << 1 | 1, mid + 1, r);
  } else
    __query(rt << 1, l, mid);
}
int query() {
  now = I, res = 1;
  __query(1, 0, n - 1);
  return res;
}
}  // namespace SgT
int ind[200010];
bool is_line = true;
int main() {
  n = read();
  for (int i = 1; i <= n; ++i) {
    w[i] = read();
    ret[w[i]] = top[i] = i;
  }
  for (int i = 2; i <= n; ++i) {
    fa[i] = read();
    addedge(fa[i], i);
    ++ind[fa[i]], ++ind[i];
    if (ind[fa[i]] > 2 || ind[i] > 2) is_line = false;
  }
  dfs(1);
  for (int i = 1; i <= n; ++i) find(i);
  SgT::build(1, 0, n - 1);
  m = read();
  while (m-- > 0) {
    static int op, x, y;
    op = read();
    if (op == 1) {
      x = read(), y = read();
      std::swap(ret[w[x]], ret[w[y]]), std::swap(w[x], w[y]);
      if (!is_line) SgT::modify(w[x]), SgT::modify(w[y]);
    } else
      printf("%d\n", is_line ? n : SgT::query());
  }
  return 0;
}

### Prompt

In CPP, your task is to solve 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>
namespace __IO {
int ch;
inline int read() {
  static int x;
  while (isspace(ch = getchar()))
    ;
  x = ch & 15;
  while (isdigit(ch = getchar())) x = x * 10 + (ch & 15);
  return x;
}
}  // namespace __IO
using __IO::read;
int head[200010], cnt;
struct Edge {
  int to, nxt;
} e[200010];
inline void addedge(int a, int b) {
  e[++cnt] = (Edge){b, head[a]};
  head[a] = cnt;
}
int fa[200010], sz[200010], dep[200010];
int top[200010], dfn[200010], idx;
int find(int x) { return x == top[x] ? x : (top[x] = find(top[x])); }
void dfs(int u) {
  int son = 0;
  dfn[u] = ++idx, sz[u] = 1;
  for (int i = head[u], v; i; i = e[i].nxt) {
    v = e[i].to;
    dep[v] = dep[u] + 1;
    dfs(v), sz[u] += sz[v];
    if (sz[v] > sz[son]) son = v;
  }
  if (son) top[son] = u;
}
inline int LCA(int x, int y) {
  while (top[x] != top[y]) {
    if (dep[top[x]] > dep[top[y]])
      x = fa[top[x]];
    else
      y = fa[top[y]];
  }
  return dep[x] < dep[y] ? x : y;
}
int n, m, w[200010], ret[200010];
inline bool in_sub(int x, int y) {
  return (dfn[x] >= dfn[y]) && (dfn[x] < dfn[y] + sz[y]);
}
inline bool in_line(int x, int y, int z) {
  static int lca;
  lca = LCA(x, y);
  return in_sub(z, lca) && (in_sub(x, z) || in_sub(y, z));
}
inline bool in_line(int x, int y, int l, int r) {
  return in_line(x, y, l) && in_line(x, y, r);
}
struct node {
  bool line;
  int l, r;
  inline node() {}
  inline node(int __l) : line(true), l(__l), r(__l) {}
  inline node(int __l, int __r) : line(true), l(__l), r(__r) {}
  inline node(bool __line, int __l, int __r) : line(__line), l(__l), r(__r) {}
  static inline node NS() { return node(0, -1, -1); }
  inline node operator+(const node &rhs) const {
    if (!l || !r) return rhs;
    if (!line || !rhs.line) return NS();
    const int x = rhs.l, y = rhs.r;
    if (in_line(l, r, x, y)) return node(l, r);
    if (in_line(l, x, r, y)) return node(l, x);
    if (in_line(l, y, x, r)) return node(l, y);
    if (in_line(r, x, l, y)) return node(r, x);
    if (in_line(r, y, l, x)) return node(r, y);
    if (in_line(x, y, l, r)) return node(x, y);
    return NS();
  }
} I(0, 0, 0);
namespace SgT {
node V[200010 << 2];
void build(const int rt, const int l, const int r) {
  if (l == r) {
    V[rt] = node(ret[l]);
    return;
  }
  const int mid = l + r >> 1;
  build(rt << 1, l, mid), build(rt << 1 | 1, mid + 1, r);
  V[rt] = V[rt << 1] + V[rt << 1 | 1];
}
int pos;
void __modify(const int rt, const int l, const int r) {
  if (l == r) {
    V[rt] = node(ret[l]);
    return;
  }
  const int mid = l + r >> 1;
  if (pos <= mid)
    __modify(rt << 1, l, mid);
  else
    __modify(rt << 1 | 1, mid + 1, r);
  V[rt] = V[rt << 1] + V[rt << 1 | 1];
}
void modify(const int __pos) {
  pos = __pos;
  __modify(1, 0, n - 1);
}
node now;
int res;
void __query(int rt, int l, int r) {
  if (l == r) {
    res = l;
    return;
  }
  node tmp = now + V[rt << 1];
  const int mid = l + r >> 1;
  if (tmp.line) {
    now = tmp;
    __query(rt << 1 | 1, mid + 1, r);
  } else
    __query(rt << 1, l, mid);
}
int query() {
  now = I, res = 1;
  __query(1, 0, n - 1);
  return res;
}
}  // namespace SgT
int ind[200010];
bool is_line = true;
int main() {
  n = read();
  for (int i = 1; i <= n; ++i) {
    w[i] = read();
    ret[w[i]] = top[i] = i;
  }
  for (int i = 2; i <= n; ++i) {
    fa[i] = read();
    addedge(fa[i], i);
    ++ind[fa[i]], ++ind[i];
    if (ind[fa[i]] > 2 || ind[i] > 2) is_line = false;
  }
  dfs(1);
  for (int i = 1; i <= n; ++i) find(i);
  SgT::build(1, 0, n - 1);
  m = read();
  while (m-- > 0) {
    static int op, x, y;
    op = read();
    if (op == 1) {
      x = read(), y = read();
      std::swap(ret[w[x]], ret[w[y]]), std::swap(w[x], w[y]);
      if (!is_line) SgT::modify(w[x]), SgT::modify(w[y]);
    } else
      printf("%d\n", is_line ? n : SgT::query());
  }
  return 0;
}

```