시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 (추가 시간 없음) 512 MB111100.000%

문제

You have a tree consisting of $n$ nodes labeled from $1$ to $n$. The tree is rooted at node $1$. A function $cnt(v, l, r)$ is defined as the number of nodes in a subtree of node $v$, that have indices from $l$ to $r$ inclusive. You are required to answer $q$ queries. The query is represented by a pair $(l_i, r_i)$. The answer to the query is a sum $\sum_{l \le i \le r} cnt(i, l, r)$.

입력

First line contains an integer $n$ --- the number of nodes in the tree.

Next $n - 1$ lines indicate ancestors of the nodes in the tree. Each $i$-th line of those $n - 1$ lines contains the ancestor's index for the $i + 1$-th node in the tree.

The following line contains a single integer $q$ --- the number of queries to be answered.

Each of the next $q$ lines contains two numbers $u_i$ and $v_i$ --- encoded queries.

출력

Print $q$ lines. The $i$-th line should contain the answer to the query $(l_i, r_i)$.

제한

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

Let $ans_i$ be the answer to the $i$-th query ($ans_0 = 0$). Then, the parameters of the  $i$-th query are:

  • $ 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) $

예제 입력 1

9
1
2
3
4
5
5
7
8
5
0 8
1 2
2 3
4 5
6 7

예제 출력 1

42
8
3
3
3