Il existe un arbre pondéré composé de $N$ sommets, numérotés de $0$ à $N - 1$. Pour tout $i$ tel que $1 \leq i \leq N-1$, le sommet $i$ est relié à son parent $P[i]$ ($P[i] < i$) par une arête de poids $W[i]$ ($W[i] \geq 0$). Notez que le sommet $0$ n'a pas de parent et, par commodité, nous posons $P[0] = W[0] = -1$.

Le seul moyen pour Sasaki de se déplacer entre les sommets de l'arbre est la téléportation. Avec une énergie $e$, Sasaki peut se téléporter du sommet $u$ au sommet $v$ si et seulement si toutes les conditions suivantes sont remplies :

• Soit $u$ est un ancêtre de $v$, soit $v$ est un ancêtre de $u$, ET
• Le XOR bit à bit de tous les poids des arêtes situées entre $u$ et $v$ est au plus $e$.

Notez que la téléportation ne consomme aucune énergie ; Sasaki conserve son énergie $e$ après chaque téléportation.

Quand $u$ est-il un ancêtre de $v$ ? Le sommet $u$ est un ancêtre de $v$ si au moins l'une des conditions suivantes est vraie :

• le sommet $u$ est le sommet $v$ ($u = v$), OU
• le sommet $u$ est le parent du sommet $v$ ($u = P[v]$), OU
• le sommet $u$ est le parent du parent du sommet $v$ ($u = P[P[v]]$), OU
• le sommet $u$ est le parent du parent du parent du sommet $v$ ($u = P[P[P[v]]]$), OU
• etc.

Qu'est-ce que le XOR bit à bit ? Le XOR bit à bit de deux entiers non négatifs $a$ et $b$, noté $a \oplus b$, est défini comme suit : lorsque $a \oplus b$ est écrit en base deux, le chiffre à la position $2^k$ est $1$ si exactement l'un des chiffres à la position $2^k$ de $a$ et $b$ est $1$, et $0$ sinon. Par exemple :

• $3 \oplus 5 = 6$ (en base deux : $011 \oplus 101 = 110$).
• $4 \oplus 21 = 17$ (en base deux : $100 \oplus 10101 = 10001$). Le XOR bit à bit de plusieurs entiers $A[0], A[1], \ldots, A[K-1]$ est défini comme $A[0] \oplus A[1] \oplus A[2] \oplus \ldots \oplus A[K-1]$. Notez que $\oplus$ est un opérateur commutatif et associatif. C'est-à-dire que $a \oplus b = b \oplus a$ et $(a \oplus b) \oplus c = a \oplus (b \oplus c)$. L'ordre dans lequel nous arrangeons les entiers ou appliquons l'opération XOR n'a donc aucune importance pour obtenir le résultat final.

Miyano doit répondre à $Q$ requêtes. Chaque requête est spécifiée par une paire d'entiers $U$ et $V$. La tâche de Miyano est de calculer l'énergie minimale dont Sasaki a besoin pour aller du sommet $U$ au sommet $V$ en utilisant zéro ou plusieurs opérations de téléportation.

Détails d'implémentation

Vous devez implémenter la procédure suivante :

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

• $N$ : le nombre de sommets de l'arbre.
• $P$, $W$ : tableaux d'entiers de longueur $N$ spécifiant les parents de chaque sommet et le poids de l'arête les reliant.
• Cette procédure est appelée exactement une fois au début, avant tout appel à minimum_energy.

int minimum_energy(int U, int V)

• $U$, $V$ : la paire d'entiers décrivant une requête.
• Cette procédure est appelée exactement $Q$ fois après l'invocation de init.
• Cette procédure doit renvoyer la réponse à la requête donnée.

Contraintes

• $2 \leq N \leq 50\;000$.
• $1 \leq Q \leq 100\;000$.
• $P[0] = -1$.
• $0 \leq P[i] < i$, pour tout $0 \leq i < N$.
• $W[0] = -1$.
• $0 \leq W[i] < 2^{20}$, pour tout $0 \leq i < N$.
• $0 \leq U, V < N$ dans chaque requête.

Sous-tâches

1. (5 points) $N \leq 10$.
2. (9 points) $W[i] \leq 1$, pour tout $0 \leq i < N$.
3. (15 points) $N \leq 200$.
4. (28 points) $W[i] < 128$, pour tout $0 \leq i < N$.
5. (28 points) $N \leq 10\;000$.
6. (15 points) Aucune contrainte supplémentaire.

Exemples

Considérez les appels suivants :

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

L'arbre est composé de $6$ sommets, illustrés ci-dessous.

Entrée 1

minimum_energy(2, 4)

Sortie 1

1

Remarque

Sasaki peut se déplacer du sommet $2$ au sommet $4$ avec une énergie de $1$ en utilisant les téléportations comme suit :

• Téléportation du sommet $2$ au sommet $0$. Le sommet $0$ est un ancêtre du sommet $2$ et le XOR bit à bit des poids des arêtes du sommet $2$ au sommet $0$ est $2 \oplus 3 = 1$.
• Téléportation du sommet $0$ au sommet $4$. Le sommet $0$ est un ancêtre du sommet $4$ et le XOR bit à bit des poids des arêtes du sommet $0$ au sommet $4$ est $3 \oplus 2 = 1$.

Il n'existe aucune autre séquence de téléportations utilisant strictement moins d'énergie. Par conséquent, cet appel doit renvoyer $1$.

Entrée 2

minimum_energy(3, 0)

Sortie 2

0

Remarque

Sasaki peut se déplacer du sommet $3$ au sommet $0$ avec une énergie de $0$ en utilisant les téléportations comme suit :

• Téléportation du sommet $3$ au sommet $0$. Le sommet $0$ est un ancêtre du sommet $3$ et le XOR bit à bit des poids des arêtes du sommet $3$ au sommet $0$ est $0$.

Par conséquent, cet appel doit renvoyer $0$.

Entrée 3

minimum_energy(1, 1)

Sortie 3

0

Remarque

Comme les sommets de départ et d'arrivée sont tous deux le sommet $1$, Sasaki n'a besoin d'effectuer aucune téléportation, ce qui nécessite une énergie nulle. Par conséquent, cet appel doit renvoyer $0$.

Entrée 4

minimum_energy(0, 5)

Sortie 4

0

Remarque

Sasaki peut se déplacer du sommet $0$ au sommet $5$ avec une énergie de $0$ en utilisant les téléportations comme suit :

• Téléportation du sommet $0$ au sommet $5$. Le sommet $0$ est un ancêtre du sommet $5$ et le XOR bit à bit des poids des arêtes du sommet $0$ au sommet $5$ est $3 \oplus 2 \oplus 1 = 0$.

Par conséquent, cet appel doit renvoyer $0$.

Grader

Format d'entrée :

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]

où $U[j]$ et $V[j]$, pour tout $0 \leq j < Q$, sont les arguments d'entrée pour le $j$-ième appel à minimum_energy.

Format de sortie :

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

où $A[j]$ est la réponse à la requête $j$, pour chaque $j$ tel que $0 \leq j < Q$.