有一棵邊權樹，包含 $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$ 路徑上所有邊權的位元互斥或（bitwise XOR）值至多為 $e$。

注意，瞬間移動不會消耗任何能量；Sasaki 在每次瞬間移動後仍保有能量 $e$。

何時 $u$ 是 $v$ 的祖先？ 若以下至少一個條件為真，則頂點 $u$ 是 $v$ 的祖先：

• 頂點 $u$ 即為頂點 $v$ ($u = v$)，或
• 頂點 $u$ 是頂點 $v$ 的父節點 ($u = P[v]$)，或
• 頂點 $u$ 是頂點 $v$ 的父節點的父節點 ($u = P[P[v]]$)，或
• 頂點 $u$ 是頂點 $v$ 的父節點的父節點的父節點 ($u = P[P[P[v]]]$)，或
• 等等。

什麼是位元互斥或（bitwise XOR）？ 兩個非負整數 $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)$。因此，排列整數的順序或進行 XOR 的順序都不會影響最終的位元互斥或結果。

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 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$ 的邊權位元互斥或為 $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$。

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]

其中對於所有 $0 \leq j < Q$，$U[j]$ 與 $V[j]$ 為第 $j$ 次呼叫 minimum_energy 的輸入參數。

輸出格式：

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

其中 $A[j]$ 為第 $j$ 個詢問的答案，對於每個 $0 \leq j < Q$。