Дан взвешенный ориентированный граф в виде дерева с $N$ вершинами, пронумерованными от $0$ до $N - 1$. Для каждого $i$, такого что $1 \leq i \leq N-1$, вершина $i$ соединена со своим родителем $P[i]$ ($P[i] < i$) ребром весом $W[i]$ ($W[i] \geq 0$). Заметим, что у вершины $0$ нет родителя, поэтому для удобства мы полагаем $P[0] = W[0] = -1$.

Единственный способ перемещения Сасаки между вершинами дерева — телепортация. Обладая энергией $e$, Сасаки может телепортироваться из вершины $u$ в вершину $v$ тогда и только тогда, когда выполняются все следующие условия:

• Либо $u$ является предком $v$, либо $v$ является предком $u$, И
• Побитовое исключающее ИЛИ (XOR) всех весов ребер на пути от $u$ до $v$ не превышает $e$.

Заметим, что телепортация не расходует энергию; после каждой телепортации у Сасаки остается та же энергия $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]]]$), ИЛИ
• и так далее.

Что такое побитовое XOR? Побитовое исключающее ИЛИ двух неотрицательных целых чисел $a$ и $b$, обозначаемое как $a \oplus b$, определяется следующим образом: если записать $a \oplus b$ в двоичной системе счисления, то цифра в разряде $2^k$ равна $1$, если ровно одна из цифр в разряде $2^k$ чисел $a$ и $b$ равна $1$, и $0$ в противном случае. Например:

• $3 \oplus 5 = 6$ (в двоичной системе: $011 \oplus 101 = 110$).
• $4 \oplus 21 = 17$ (в двоичной системе: $100 \oplus 10101 = 10001$). Побитовое XOR нескольких целых чисел $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 не влияют на результат.

Мияно должна ответить на $Q$ запросов. Каждый запрос задается парой целых чисел $U$ и $V$. Задача Мияно — вычислить минимальную энергию, необходимую Сасаки для перемещения из вершины $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$: пара целых чисел, описывающих запрос.
• Эта процедура вызывается ровно $Q$ раз после вызова init.
• Эта процедура должна возвращать ответ на заданный запрос.

Ограничения

• $2 \leq N \leq 50\,000$.
• $1 \leq Q \leq 100\,000$.
• $P[0] = -1$.
• $0 \leq P[i] < i$ для всех $0 \leq i < N$.
• $W[0] = -1$.
• $0 \leq W[i] < 2^{20}$ для всех $0 \leq i < N$.
• $0 \leq U, V < N$ в каждом запросе.

Подзадачи

1. (5 баллов) $N \leq 10$.
2. (9 баллов) $W[i] \leq 1$ для всех $0 \leq i < N$.
3. (15 баллов) $N \leq 200$.
4. (28 баллов) $W[i] < 128$ для всех $0 \leq i < N$.
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)

Сасаки может переместиться из вершины $2$ в вершину $4$ с энергией $1$, используя следующие телепортации:

• Телепортация из вершины $2$ в вершину $0$. Вершина $0$ является предком вершины $2$, а побитовое XOR весов ребер от вершины $2$ до вершины $0$ равно $2 \oplus 3 = 1$.
• Телепортация из вершины $0$ в вершину $4$. Вершина $0$ является предком вершины $4$, а побитовое XOR весов ребер от вершины $0$ до вершины $4$ равно $3 \oplus 2 = 1$.

Других последовательностей телепортаций, использующих строго меньше энергии, не существует. Поэтому данный вызов должен вернуть $1$.

minimum_energy(3, 0)

Сасаки может переместиться из вершины $3$ в вершину $0$ с энергией $0$, используя следующие телепортации:

• Телепортация из вершины $3$ в вершину $0$. Вершина $0$ является предком вершины $3$, а побитовое XOR весов ребер от вершины $3$ до вершины $0$ равно $0$.

Поэтому данный вызов должен вернуть $0$.

minimum_energy(1, 1)

Так как начальная и конечная вершины совпадают (вершина $1$), Сасаки не нужно совершать никаких телепортаций, что требует нулевой энергии. Поэтому данный вызов должен вернуть $0$.

minimum_energy(0, 5)

Сасаки может переместиться из вершины $0$ в вершину $5$ с энергией $0$, используя следующие телепортации:

• Телепортация из вершины $0$ в вершину $5$. Вершина $0$ является предком вершины $5$, а побитовое XOR весов ребер от вершины $0$ до вершины $5$ равно $3 \oplus 2 \oplus 1 = 0$.

Поэтому данный вызов должен вернуть $0$.