Existe un árbol con pesos en las aristas que consta de $N$ vértices, numerados del $0$ al $N - 1$. Para cada $i$, tal que $1 \leq i \leq N-1$, el vértice $i$ está conectado a su padre $P[i]$ ($P[i] < i$) con una arista de peso $W[i]$ ($W[i] \geq 0$). Nótese que el vértice $0$ no tiene padre y, por conveniencia, establecemos $P[0] = W[0] = -1$.

La única forma en que Sasaki puede moverse entre los vértices del árbol es mediante teletransportación. Con una energía $e$, Sasaki puede teletransportarse del vértice $u$ al vértice $v$ si y solo si se cumplen todas las siguientes condiciones:

• O bien $u$ es un ancestro de $v$, o $v$ es un ancestro de $u$, Y
• El XOR bit a bit de todos los pesos de las aristas desde $u$ hasta $v$ es como máximo $e$.

Nótese que la teletransportación no consume energía; Sasaki sigue teniendo energía $e$ después de cada teletransportación.

¿Cuándo es $u$ un ancestro de $v$? El vértice $u$ es un ancestro de $v$ si al menos una de las siguientes condiciones es verdadera:

• el vértice $u$ es el vértice $v$ ($u = v$), O
• el vértice $u$ es el padre del vértice $v$ ($u = P[v]$), O
• el vértice $u$ es el padre del padre del vértice $v$ ($u = P[P[v]]$), O
• el vértice $u$ es el padre del padre del padre del vértice $v$ ($u = P[P[P[v]]]$), O
• etcétera.

¿Qué es el XOR bit a bit? El XOR bit a bit de dos enteros no negativos $a$ y $b$, denotado como $a \oplus b$, se define de la siguiente manera: cuando $a \oplus b$ se escribe en base dos, el dígito en la posición $2^k$ es $1$ si exactamente uno de los dígitos en la posición $2^k$ de $a$ y $b$ es $1$, y $0$ en caso contrario. Por ejemplo:

• $3 \oplus 5 = 6$ (en base dos: $011 \oplus 101 = 110$).
• $4 \oplus 21 = 17$ (en base dos: $100 \oplus 10101 = 10001$). El XOR bit a bit de múltiples enteros $A[0], A[1], \ldots, A[K-1]$ se define como $A[0] \oplus A[1] \oplus A[2] \oplus \ldots \oplus A[K-1]$. Nótese que $\oplus$ es un operador conmutativo y asociativo. Es decir, $a \oplus b = b \oplus a$ y $(a \oplus b) \oplus c = a \oplus (b \oplus c)$ respectivamente. Por lo tanto, no importa en qué orden organicemos los enteros, ni en qué orden apliquemos el XOR a los enteros para obtener el XOR bit a bit final.

Miyano debe responder $Q$ consultas. Cada consulta se especifica mediante un par de enteros $U$ y $V$. La tarea de Miyano es calcular la energía mínima que Sasaki necesita para ir del vértice $U$ al vértice $V$ utilizando cero o más operaciones de teletransportación.

Detalles de implementación

Debe implementar el siguiente procedimiento:

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

• $N$: el número de vértices del árbol.
• $P$, $W$: arreglos de enteros de longitud $N$ que especifican los padres de cada vértice y el peso de la arista que los conecta.
• Este procedimiento se llama exactamente una vez al principio, antes de cualquier llamada a minimum_energy.

int minimum_energy(int U, int V)

• $U$, $V$: el par de enteros que describen una consulta.
• Este procedimiento se llama exactamente $Q$ veces después de la invocación de init.
• Este procedimiento debe devolver la respuesta a la consulta dada.

Restricciones

• $2 \leq N \leq 50\;000$.
• $1 \leq Q \leq 100\;000$.
• $P[0] = -1$.
• $0 \leq P[i] < i$, para todo $0 \leq i < N$.
• $W[0] = -1$.
• $0 \leq W[i] < 2^{20}$, para todo $0 \leq i < N$.
• $0 \leq U, V < N$ en cada consulta.

Subtareas

1. (5 puntos) $N \leq 10$.
2. (9 puntos) $W[i] \leq 1$, para todo $0 \leq i < N$.
3. (15 puntos) $N \leq 200$.
4. (28 puntos) $W[i] < 128$, para todo $0 \leq i < N$.
5. (28 puntos) $N \leq 10\;000$.
6. (15 puntos) Sin restricciones adicionales.

Ejemplos

Considere las siguientes llamadas:

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

El árbol consta de $6$ vértices, los cuales se ilustran a continuación.

Entrada 1

minimum_energy(2, 4)

Salida 1

1

Nota

Sasaki puede moverse del vértice $2$ al vértice $4$ con energía $1$ usando las teletransportaciones de la siguiente manera:

• Teletransportarse del vértice $2$ al vértice $0$. El vértice $0$ es un ancestro del vértice $2$ y el XOR bit a bit del peso de las aristas desde el vértice $2$ hasta el vértice $0$ es $2 \oplus 3 = 1$.
• Teletransportarse del vértice $0$ al vértice $4$. El vértice $0$ es un ancestro del vértice $4$ y el XOR bit a bit del peso de las aristas desde el vértice $0$ hasta el vértice $4$ es $3 \oplus 2 = 1$.

No existen otras secuencias de teletransportaciones que utilicen estrictamente menos energía. Por lo tanto, esta llamada debe devolver $1$.

Entrada 2

minimum_energy(3, 0)

Salida 2

0

Nota

Sasaki puede moverse del vértice $3$ al vértice $0$ con energía $0$ usando las teletransportaciones de la siguiente manera:

• Teletransportarse del vértice $3$ al vértice $0$. El vértice $0$ es un ancestro del vértice $3$ y el XOR bit a bit del peso de las aristas desde el vértice $3$ hasta el vértice $0$ es $0$.

Por lo tanto, esta llamada debe devolver $0$.

Entrada 3

minimum_energy(1, 1)

Salida 3

0

Nota

Dado que los vértices de inicio y fin son ambos el vértice $1$, Sasaki no necesita realizar ninguna teletransportación, lo cual requiere cero energía. Por lo tanto, esta llamada debe devolver $0$.

Entrada 4

minimum_energy(0, 5)

Salida 4

0

Nota

Sasaki puede moverse del vértice $0$ al vértice $5$ con energía $0$ usando las teletransportaciones de la siguiente manera:

• Teletransportarse del vértice $0$ al vértice $5$. El vértice $0$ es un ancestro del vértice $5$ y el XOR bit a bit del peso de las aristas desde el vértice $0$ hasta el vértice $5$ es $3 \oplus 2 \oplus 1 = 0$.

Por lo tanto, esta llamada debe devolver $0$.

Evaluador de muestra

Formato de entrada:

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]

donde $U[j]$ y $V[j]$, para todo $0 \leq j < Q$, son los argumentos de entrada para la $j$-ésima llamada a minimum_energy.

Formato de salida:

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

donde $A[j]$ es la respuesta a la consulta $j$, para cada $j$ tal que $0 \leq j < Q$.