Dane jest drzewo o krawędziach z wagami, składające się z $N$ wierzchołków ponumerowanych od $0$ do $N - 1$. Dla każdego $i$, takiego że $1 \leq i \leq N-1$, wierzchołek $i$ jest połączony ze swoim rodzicem $P[i]$ ($P[i] < i$) krawędzią o wadze $W[i]$ ($W[i] \geq 0$). Zauważ, że wierzchołek $0$ nie posiada rodzica, dlatego dla wygody przyjmujemy $P[0] = W[0] = -1$.

Jedynym sposobem poruszania się Sasakiego między wierzchołkami drzewa jest teleportacja. Dysponując energią $e$, Sasaki może przeteleportować się z wierzchołka $u$ do wierzchołka $v$ wtedy i tylko wtedy, gdy spełnione są wszystkie poniższe warunki:

• $u$ jest przodkiem $v$ lub $v$ jest przodkiem $u$, ORAZ
• Bitowa suma XOR wszystkich wag krawędzi na ścieżce między $u$ a $v$ wynosi co najwyżej $e$.

Zauważ, że teleportacja nie zużywa energii; Sasaki zachowuje energię $e$ po każdej teleportacji.

Kiedy $u$ jest przodkiem $v$? Wierzchołek $u$ jest przodkiem $v$, jeśli spełniony jest co najmniej jeden z poniższych warunków:

• wierzchołek $u$ jest wierzchołkiem $v$ ($u = v$), LUB
• wierzchołek $u$ jest rodzicem wierzchołka $v$ ($u = P[v]$), LUB
• wierzchołek $u$ jest rodzicem rodzica wierzchołka $v$ ($u = P[P[v]]$), LUB
• wierzchołek $u$ jest rodzicem rodzica rodzica wierzchołka $v$ ($u = P[P[P[v]]]$), LUB
• itd.

Czym jest bitowa suma XOR? Bitowa suma XOR dwóch nieujemnych liczb całkowitych $a$ oraz $b$, oznaczana jako $a \oplus b$, jest zdefiniowana następująco: - Gdy $a \oplus b$ zapiszemy w systemie dwójkowym, cyfra na pozycji $2^k$ wynosi $1$, jeśli dokładnie jedna z cyfr na pozycji $2^k$ w liczbach $a$ i $b$ wynosi $1$, a w przeciwnym razie wynosi $0$. Na przykład:

• $3 \oplus 5 = 6$ (w systemie dwójkowym: $011 \oplus 101 = 110$).
• $4 \oplus 21 = 17$ (w systemie dwójkowym: $100 \oplus 10101 = 10001$). Bitowa suma XOR wielu liczb całkowitych $A[0], A[1], \ldots, A[K-1]$ jest zdefiniowana jako $A[0] \oplus A[1] \oplus A[2] \oplus \ldots \oplus A[K-1]$. Zauważ, że $\oplus$ jest operatorem przemiennym i łącznym. Oznacza to, że $a \oplus b = b \oplus a$ oraz $(a \oplus b) \oplus c = a \oplus (b \oplus c)$. Zatem kolejność liczb oraz kolejność wykonywania operacji XOR nie mają wpływu na wynik końcowy.

Miyano musi odpowiedzieć na $Q$ zapytań. Każde zapytanie jest określone parą liczb całkowitych $U$ i $V$. Zadaniem Miyano jest obliczenie minimalnej energii, której Sasaki potrzebuje, aby przemieścić się z wierzchołka $U$ do wierzchołka $V$, wykonując zero lub więcej operacji teleportacji.

Szczegóły implementacji

Należy zaimplementować następujące procedury:

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

• $N$: liczba wierzchołków drzewa.
• $P$, $W$: tablice liczb całkowitych o długości $N$, określające rodziców każdego wierzchołka oraz wagę krawędzi łączącej je.
• Ta procedura jest wywoływana dokładnie raz na początku, przed jakimkolwiek wywołaniem minimum_energy.

int minimum_energy(int U, int V)

• $U$, $V$: para liczb całkowitych opisująca zapytanie.
• Ta procedura jest wywoływana dokładnie $Q$ razy po wywołaniu init.
• Ta procedura powinna zwrócić odpowiedź na dane zapytanie.

Ograniczenia

• $2 \leq N \leq 50\;000$.
• $1 \leq Q \leq 100\;000$.
• $P[0] = -1$.
• $0 \leq P[i] < i$, dla wszystkich $0 \leq i < N$.
• $W[0] = -1$.
• $0 \leq W[i] < 2^{20}$, dla wszystkich $0 \leq i < N$.
• $0 \leq U, V < N$ w każdym zapytaniu.

Podzadania

1. (5 punktów) $N \leq 10$.
2. (9 punktów) $W[i] \leq 1$, dla wszystkich $0 \leq i < N$.
3. (15 punktów) $N \leq 200$.
4. (28 punktów) $W[i] < 128$, dla wszystkich $0 \leq i < N$.
5. (28 punktów) $N \leq 10\;000$.
6. (15 punktów) Brak dodatkowych ograniczeń.

Przykład

Rozważmy następujące wywołania:

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

Drzewo składa się z $6$ wierzchołków, co zilustrowano poniżej:

minimum_energy(2, 4)

Sasaki może przemieścić się z wierzchołka $2$ do wierzchołka $4$ z energią $1$, używając następujących teleportacji:

• Teleportacja z wierzchołka $2$ do wierzchołka $0$. Wierzchołek $0$ jest przodkiem wierzchołka $2$, a bitowa suma XOR wag krawędzi od wierzchołka $2$ do $0$ wynosi $2 \oplus 3 = 1$.
• Teleportacja z wierzchołka $0$ do wierzchołka $4$. Wierzchołek $0$ jest przodkiem wierzchołka $4$, a bitowa suma XOR wag krawędzi od wierzchołka $0$ do $4$ wynosi $3 \oplus 2 = 1$.

Nie istnieją inne sekwencje teleportacji, które zużywają mniej energii. Zatem to wywołanie powinno zwrócić $1$.

minimum_energy(3, 0)

Sasaki może przemieścić się z wierzchołka $3$ do wierzchołka $0$ z energią $0$, używając następującej teleportacji:

• Teleportacja z wierzchołka $3$ do wierzchołka $0$. Wierzchołek $0$ jest przodkiem wierzchołka $3$, a bitowa suma XOR wag krawędzi od wierzchołka $3$ do $0$ wynosi $0$.

Zatem to wywołanie powinno zwrócić $0$.

minimum_energy(1, 1)

Ponieważ wierzchołek startowy i końcowy to ten sam wierzchołek $1$, Sasaki nie musi wykonywać żadnych teleportacji, co wymaga zerowej energii. Zatem to wywołanie powinno zwrócić $0$.

minimum_energy(0, 5)

Sasaki może przemieścić się z wierzchołka $0$ do wierzchołka $5$ z energią $0$, używając następującej teleportacji:

• Teleportacja z wierzchołka $0$ do wierzchołka $5$. Wierzchołek $0$ jest przodkiem wierzchołka $5$, a bitowa suma XOR wag krawędzi od wierzchołka $0$ do $5$ wynosi $3 \oplus 2 \oplus 1 = 0$.

Zatem to wywołanie powinno zwrócić $0$.

Wejście

Format wejścia:

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]

gdzie $U[j]$ oraz $V[j]$, dla wszystkich $0 \leq j < Q$, są argumentami wejściowymi dla $j$-tego wywołania minimum_energy.

Wyjście

Format wyjścia:

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

gdzie $A[j]$ jest odpowiedzią na zapytanie $j$, dla każdego $j$ takiego, że $0 \leq j < Q$.