There are nodes with IDs from to . All nodes, with the exception of Node , has a parent node with an ID less than itself. Each node has a value. The node has a value of .
A ancestor of a node is defined as follows:
- If , the parent of the node
- If , the parent of the ancestor of the node
Two nodes are considered cousins if and only if their ancestors both exist and are the same node.
A node 's cousins is the set of all nodes for which and are cousins.
Answer queries, each asking: "Given and , what is the sum of the values cousins of ?"
Constraints
Input Specification
The first line contains and .
The second line contains integers, the integer being .
The third line contains integers, the parents of Node to Node .
The next lines contain two integers each, and .
Output Specification
Print lines, the answers to the queries, in the order that they are given.
Sample Input
9 2
1 2 4 8 16 32 64 128 256
1 1 3 3 3 4 6 6
6 1
8 2
Sample Output
24
320
Comments