친자 확인

노드 $1$번부터 $n$번까지 번호가 붙은 $n$개의 노드로 이루어진 트리가 있다. 트리의 루트는 $1$번 노드다. 함수 $cnt(v, l, r)$은 노드 $v$의 서브트리에 속하면서 번호가 $l$ 이상 $r$ 이하인 노드의 개수로 정의한다. $q$개의 질의에 답해야 한다. 질의는 순서쌍 $(l_i, r_i)$로 주어진다. 질의의 답은 합 $\sum_{l \le i \le r} cnt(i, l, r)$이다.

첫째 줄에 정수 $n$이 주어진다. 이는 트리의 노드 개수다.

다음 $n - 1$개의 줄에는 트리에서 각 노드의 부모가 주어진다. 이 $n - 1$개의 줄 중 $i$번째 줄에는 $i + 1$번 노드의 부모 번호가 들어 있다.

그다음 줄에는 정수 $q$가 하나 주어진다. 이는 답해야 하는 질의의 개수다.

다음 $q$개의 줄에는 인코딩된 질의를 나타내는 두 수 $u_i$와 $v_i$가 주어진다.

$q$개의 줄을 출력한다. $i$번째 줄에는 질의 $(l_i, r_i)$의 답을 출력한다.

• $1 \le n \le 50000$
• $1 \le q \le 50000$
• $0 \le u_i, v_i \le 10^9$

$ans_i$를 $i$번째 질의의 답이라 하자($ans_0 = 0$). 그러면 $i$번째 질의의 매개변수는 다음과 같다.

• $x_i = 1 + ((u_i \oplus ans_{i-1}) \mod n)$
• $y_i = 1 + ((v_i \oplus ans_{i-1}) \mod n)$
• $l_i = min(x_i, y_i)$
• $r_i = max(x_i, y_i)$