After a long day at school, Andy went home to visit his favourite tree.

This tree will grow every day. Let's call $T_x$ the tree on day $x$. The initial tree is $T_0$, which consists of $N$ nodes. Every day, each leaf node will be replaced with a subtree identical to $T_0$.

Nodes in the tree will be given indices based on their preorder traversal. Note that the tree given is not necessarily a binary tree.

For example, the following graph shows a possible tree $T_0$, followed by $T_1$, and followed by an illustration of how nodes in $T_1$ would be ordered according to its preorder traversal:

This tree has already been growing for $K$ days, meaning the current tree is $T_k$. Andy will ask you $Q$ queries about the length of the simple path between some pair of nodes $u$ and $v$.

Recall a simple path is a path that does not have repeating vertices.

Constraints

For all subtasks:

$2\le N\le {10}^5$

$1\le Q\le {10}^5$

$0\le K\le {10}^9$

$1\le u,v\le {10}^9$

Subtask 1 [10%]

$K=0$

Subtask 2 [60%]

$K\le 30$

Subtask 3 [30%]

No additional constraints.

Input Specification

The first line contains an integer $N$, the initial number of nodes in the tree.

The second line contains $N-1$ integers. The $i^{\text{th}}$ integer is the father of node $i+1$ in $T_0$. The tree will always be rooted on node $1$. The indices of the nodes given in input are the indices according to the preorder traversal in $T_0$. It is guaranteed that the indices given in input form a valid preorder traversal in $T_0$.

The third line contains two integers $K$ and $Q$. $K$ means the tree has been growing for $K$ days, and $Q$ means the number of queries Andy will ask.

The following $Q$ lines contain two integers $u$ and $v$, meaning Andy wishes to know the length of the simple path between node $u$ and $v$.

Output Specification

For each of the $Q$ queries, output each answer on one line.

Sample Input 1

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

Sample Output 1

4
2
3
3
1

Sample Explanation 1

This is the tree formed:

Sample Input 2

10
1 2 3 4 4 3 3 3 2
2 5
10 20
15 16
89 99
12 98
100 1

Sample Output 2

4
2
9
16
10