$N$개의 정점으로 구성된 가중치 있는 트리가 있으며, 정점은 $0$부터 $N - 1$까지 번호가 매겨져 있습니다. $1 \leq i \leq N-1$인 모든 $i$에 대하여, 정점 $i$는 가중치 $W[i]$ ($W[i] \geq 0$)인 간선으로 부모 $P[i]$ ($P[i] < i$)와 연결되어 있습니다. 정점 $0$은 부모가 없으므로 편의상 $P[0] = W[0] = -1$로 설정합니다.

사사키가 트리 내의 정점 사이를 이동하는 유일한 방법은 순간이동입니다. 에너지 $e$를 사용하여 사사키가 정점 $u$에서 정점 $v$로 순간이동할 수 있는 필요충분조건은 다음 모든 조건을 만족하는 것입니다.

• $u$가 $v$의 조상이거나, $v$가 $u$의 조상이어야 함, 그리고
• $u$에서 $v$까지의 모든 간선 가중치에 대한 비트 단위 XOR 값이 최대 $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$의 비트 단위 XOR($a \oplus b$)은 다음과 같이 정의됩니다. $a \oplus b$를 이진수로 나타냈을 때, $2^k$ 자리의 숫자는 $a$와 $b$의 $2^k$ 자리 숫자 중 정확히 하나만 $1$일 때 $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]$의 비트 단위 XOR은 $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$로 주어집니다. 미야노의 과제는 사사키가 $0$회 이상의 순간이동을 사용하여 정점 $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)

사사키는 다음과 같이 순간이동을 사용하여 에너지 $1$로 정점 $2$에서 정점 $4$로 이동할 수 있습니다.

• 정점 $2$에서 정점 $0$으로 순간이동. 정점 $0$은 정점 $2$의 조상이며, 정점 $2$에서 정점 $0$까지의 간선 가중치들의 비트 단위 XOR은 $2 \oplus 3 = 1$입니다.
• 정점 $0$에서 정점 $4$로 순간이동. 정점 $0$은 정점 $4$의 조상이며, 정점 $0$에서 정점 $4$까지의 간선 가중치들의 비트 단위 XOR은 $3 \oplus 2 = 1$입니다.

이보다 적은 에너지를 사용하는 다른 순간이동 순서는 없습니다. 따라서 이 호출은 $1$을 반환해야 합니다.

minimum_energy(3, 0)

사사키는 다음과 같이 순간이동을 사용하여 에너지 $0$으로 정점 $3$에서 정점 $0$으로 이동할 수 있습니다.

• 정점 $3$에서 정점 $0$으로 순간이동. 정점 $0$은 정점 $3$의 조상이며, 정점 $3$에서 정점 $0$까지의 간선 가중치들의 비트 단위 XOR은 $0$입니다.

따라서 이 호출은 $0$을 반환해야 합니다.

minimum_energy(1, 1)

시작 정점과 끝 정점이 모두 정점 $1$이므로, 사사키는 순간이동을 할 필요가 없으며 에너지는 $0$이 필요합니다. 따라서 이 호출은 $0$을 반환해야 합니다.

minimum_energy(0, 5)

사사키는 다음과 같이 순간이동을 사용하여 에너지 $0$으로 정점 $0$에서 정점 $5$로 이동할 수 있습니다.

• 정점 $0$에서 정점 $5$로 순간이동. 정점 $0$은 정점 $5$의 조상이며, 정점 $0$에서 정점 $5$까지의 간선 가중치들의 비트 단위 XOR은 $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]$는 $0 \leq j < Q$인 각 $j$에 대한 질의 $j$의 답입니다.