你有一棵包含 $n$ 个节点的树，节点编号从 $1$ 到 $n$，根节点为 $1$。定义函数 $cnt(v, l, r)$ 为节点 $v$ 的子树中编号在 $l$ 到 $r$（包含 $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$ —— 加密后的查询。

数据范围： $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}) \pmod n)$ $y_i = 1 + ((v_i \oplus ans_{i-1}) \pmod n)$ $l_i = \min(x_i, y_i)$ $r_i = \max(x_i, y_i)$

输出格式

输出 $q$ 行。第 $i$ 行应包含查询 $(l_i, r_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