After a long day at school, Andy went home to visit his favourite tree.
This tree will grow every day. Let's call the tree on day . The initial tree is , which consists of nodes. Every day, each leaf node will be replaced with a subtree identical to .
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 , followed by , and followed by an illustration of how nodes in would be ordered according to its preorder traversal:
This tree has already been growing for days, meaning the current tree is . Andy will ask you queries about the length of the simple path between some pair of nodes and .
Recall a simple path is a path that does not have repeating vertices.
For all subtasks:
Subtask 1 [10%]
Subtask 2 [60%]
Subtask 3 [30%]
No additional constraints.
The first line contains an integer , the initial number of nodes in the tree.
The second line contains integers. The integer is the father of node in . The tree will always be rooted on node . The indices of the nodes given in input are the indices according to the preorder traversal in . It is guaranteed that the indices given in input form a valid preorder traversal in .
The third line contains two integers and . means the tree has been growing for days, and means the number of queries Andy will ask.
The following lines contain two integers and , meaning Andy wishes to know the length of the simple path between node and .
For each of the 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