$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$ までの経路上にあるすべての辺の重みのビット単位の XOR が $e$ 以下である。

テレポートによってエネルギーが消費されることはない。つまり、各テレポートの後も Sasaki はエネルギー $e$ を保持している。

$u$ が $v$ の祖先であるとは？ 以下の条件の少なくとも1つが真であるとき、頂点 $u$ は $v$ の祖先である。

• 頂点 $u$ が頂点 $v$ である ($u = v$)。または
• 頂点 $u$ が頂点 $v$ の親である ($u = P[v]$)。または
• 頂点 $u$ が頂点 $v$ の親の親である ($u = P[P[v]]$)。または
• 頂点 $u$ が頂点 $v$ の親の親の親である ($u = P[P[P[v]]]$)。または
• など。

ビット単位の XOR とは？ 2つの非負整数 $a$ と $b$ のビット単位の XOR（$a \oplus b$ と表記）は以下のように定義される。$a \oplus b$ を2進数で表記したとき、$2^k$ の位の数字は、$a$ と $b$ の $2^k$ の位の数字のどちらか一方のみが $1$ である場合に $1$ となり、それ以外の場合は $0$ となる。例：

• $3 \oplus 5 = 6$ （2進数：$011 \oplus 101 = 110$）。
• $4 \oplus 21 = 17$ （2進数：$100 \oplus 10101 = 10001$）。複数の整数 $A[0], A[1], \ldots, A[K-1]$ のビット単位の XOR は $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)$ である。したがって、整数の並び順や XOR を適用する順序は最終的な結果に影響しない。

Miyano は $Q$ 個のクエリに答える必要がある。各クエリは2つの整数 $U$ と $V$ のペアで指定される。Miyano のタスクは、0回以上のテレポート操作を用いて頂点 $U$ から頂点 $V$ へ移動するために Sasaki が必要な最小のエネルギーを計算することである。

実装の詳細

以下のプロシージャを実装すること。

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 i < N$ について $0 \leq P[i] < i$
• $W[0] = -1$
• すべての $0 \leq i < N$ について $0 \leq W[i] < 2^{20}$
• 各クエリにおいて $0 \leq U, V < N$

小課題

1. (5点) $N \leq 10$
2. (9点) すべての $0 \leq i < N$ について $W[i] \leq 1$
3. (15点) $N \leq 200$
4. (28点) すべての $0 \leq i < N$ について $W[i] < 128$
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$ までの辺の重みのビット単位 XOR は $2 \oplus 3 = 1$ である。
• 頂点 $0$ から頂点 $4$ へテレポートする。頂点 $0$ は頂点 $4$ の祖先であり、頂点 $0$ から頂点 $4$ までの辺の重みのビット単位 XOR は $3 \oplus 2 = 1$ である。

これより少ないエネルギーで移動できるテレポートの列は存在しない。したがって、この呼び出しは $1$ を返す必要がある。

minimum_energy(3, 0)

Sasaki は以下のようにテレポートすることで、エネルギー $0$ で頂点 $3$ から頂点 $0$ へ移動できる。

• 頂点 $3$ から頂点 $0$ へテレポートする。頂点 $0$ は頂点 $3$ の祖先であり、頂点 $3$ から頂点 $0$ までの辺の重みのビット単位 XOR は $0$ である。

したがって、この呼び出しは $0$ を返す必要がある。

minimum_energy(1, 1)

開始頂点と終了頂点がともに頂点 $1$ であるため、Sasaki はテレポートを行う必要がなく、必要なエネルギーは $0$ である。したがって、この呼び出しは $0$ を返す必要がある。

minimum_energy(0, 5)

Sasaki は以下のようにテレポートすることで、エネルギー $0$ で頂点 $0$ から頂点 $5$ へ移動できる。

• 頂点 $0$ から頂点 $5$ へテレポートする。頂点 $0$ は頂点 $5$ の祖先であり、頂点 $0$ から頂点 $5$ までの辺の重みのビット単位 XOR は $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]

ここで、$0 \leq j < Q$ を満たすすべての $j$ について、$U[j]$ と $V[j]$ は $j$ 回目の minimum_energy 呼び出しの入力引数である。

出力形式：

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

ここで、$A[j]$ は $0 \leq j < Q$ を満たす各 $j$ に対するクエリ $j$ の答えである。