有一个包含 $N$ 个顶点的带权树，顶点编号从 $0$ 到 $N - 1$。对于每个 $1 \leq i \leq N-1$，顶点 $i$ 与其父节点 $P[i]$ ($P[i] < i$) 相连，边权为 $W[i]$ ($W[i] \geq 0$)。注意顶点 $0$ 没有父节点，为了方便起见，我们设 $P[0] = W[0] = -1$。

Sasaki 在树的顶点间移动的唯一方式是瞬移。对于给定的能量 $e$，Sasaki 可以在满足以下所有条件时从顶点 $u$ 瞬移到顶点 $v$：

• $u$ 是 $v$ 的祖先，或者 $v$ 是 $u$ 的祖先，并且
• 从 $u$ 到 $v$ 路径上所有边权的按位异或和至多为 $e$。

注意，瞬移不消耗任何能量；每次瞬移后，Sasaki 仍然拥有能量 $e$。

什么是祖先？ 如果满足以下至少一个条件，则顶点 $u$ 是 $v$ 的祖先：

• 顶点 $u$ 就是顶点 $v$ ($u = v$)，或者
• 顶点 $u$ 是顶点 $v$ 的父节点 ($u = P[v]$)，或者
• 顶点 $u$ 是顶点 $v$ 的父节点的父节点 ($u = P[P[v]]$)，或者
• 顶点 $u$ 是顶点 $v$ 的父节点的父节点的父节点 ($u = P[P[P[v]]]$)，或者
• 等等。

什么是按位异或？ 两个非负整数 $a$ 和 $b$ 的按位异或（记作 $a \oplus b$）定义如下：当 $a \oplus b$ 用二进制表示时，若 $a$ 和 $b$ 在 $2^k$ 位上的数字恰好有一个为 $1$，则结果的 $2^k$ 位为 $1$，否则为 $0$。例如：

• $3 \oplus 5 = 6$（二进制：$011 \oplus 101 = 110$）。
• $4 \oplus 21 = 17$（二进制：$100 \oplus 10101 = 10001$）。多个整数 $A[0], A[1], \ldots, A[K-1]$ 的按位异或定义为 $A[0] \oplus A[1] \oplus A[2] \oplus \ldots \oplus A[K-1]$。注意 $\oplus$ 是满足交换律和结合律的运算符。即 $a \oplus b = b \oplus a$ 且 $(a \oplus b) \oplus c = a \oplus (b \oplus c)$。因此，排列这些整数的顺序或进行异或运算的顺序不会影响最终的按位异或结果。

Miyano 需要回答 $Q$ 个询问。每个询问由一对整数 $U$ 和 $V$ 指定。Miyano 的任务是计算 Sasaki 从顶点 $U$ 到达顶点 $V$ 所需的最小能量，可以使用零次或多次瞬移。

实现细节

你需要实现以下过程：

void init(int N, std::vector<int> P, std::vector<int> W)

• $N$：树的顶点数。
• $P, W$：长度为 $N$ 的整数数组，分别指定每个顶点的父节点以及连接它们的边权。
• 该过程在开始时恰好调用一次，在任何 minimum_energy 调用之前。

int minimum_energy(int U, int V)

• $U, V$：描述询问的一对整数。
• 该过程在 init 调用后恰好被调用 $Q$ 次。
• 该过程应返回给定询问的答案。

数据范围

• $2 \leq N \leq 50\,000$
• $1 \leq Q \leq 100\,000$
• $P[0] = -1$
• $0 \leq P[i] < i$，对于所有 $0 \leq i < N$
• $W[0] = -1$
• $0 \leq W[i] < 2^{20}$，对于所有 $0 \leq i < N$
• $0 \leq U, V < N$，对于每个询问

子任务

1. (5 分) $N \leq 10$
2. (9 分) $W[i] \leq 1$，对于所有 $0 \leq i < N$
3. (15 分) $N \leq 200$
4. (28 分) $W[i] < 128$，对于所有 $0 \leq i < N$
5. (28 分) $N \leq 10\,000$
6. (15 分) 无附加限制

样例

考虑以下调用：

init(6, [-1, 0, 1, 0, 1, 2], [-1, 3, 2, 0, 2, 1])

该树包含 $6$ 个顶点，如下图所示：

minimum_energy(2, 4)

Sasaki 可以通过以下瞬移以能量 $1$ 从顶点 $2$ 到达顶点 $4$：

• 从顶点 $2$ 瞬移到顶点 $0$。顶点 $0$ 是顶点 $2$ 的祖先，且从顶点 $2$ 到顶点 $0$ 的边权异或和为 $2 \oplus 3 = 1$。
• 从顶点 $0$ 瞬移到顶点 $4$。顶点 $0$ 是顶点 $4$ 的祖先，且从顶点 $0$ 到顶点 $4$ 的边权异或和为 $3 \oplus 2 = 1$。

没有其他使用更少能量的瞬移序列。因此，该调用应返回 $1$。

minimum_energy(3, 0)

Sasaki 可以通过以下瞬移以能量 $0$ 从顶点 $3$ 到达顶点 $0$：

• 从顶点 $3$ 瞬移到顶点 $0$。顶点 $0$ 是顶点 $3$ 的祖先，且从顶点 $3$ 到顶点 $0$ 的边权异或和为 $0$。

因此，该调用应返回 $0$。

minimum_energy(1, 1)

由于起点和终点均为顶点 $1$，Sasaki 不需要进行任何瞬移，所需能量为 $0$。因此，该调用应返回 $0$。

minimum_energy(0, 5)

Sasaki 可以通过以下瞬移以能量 $0$ 从顶点 $0$ 到达顶点 $5$：

• 从顶点 $0$ 瞬移到顶点 $5$。顶点 $0$ 是顶点 $5$ 的祖先，且从顶点 $0$ 到顶点 $5$ 的边权异或和为 $3 \oplus 2 \oplus 1 = 0$。

因此，该调用应返回 $0$。

说明

输入格式：

N
P[1] P[2] ... P[N - 1]
W[1] W[2] ... W[N - 1]
Q
U[0] V[0]
U[1] V[1]
...
U[Q - 1] V[Q - 1]

其中 $U[j]$ 和 $V[j]$（对于所有 $0 \leq j < Q$）是第 $j$ 次调用 minimum_energy 的输入参数。

输出格式：

A[0]
A[1]
...
A[Q - 1]

其中 $A[j]$ 是第 $j$ 个询问的答案（对于所有 $0 \leq j < Q$）。