The only difference between this problem and the easy version is the memory limit. However, note that the memory limit and points for this problem may be subject to change as more efficient solutions are discovered.
Recently, Angie's math teacher began teaching the class about trees (the graph theory kind, of course). As homework, he gave everyone a rooted tree of nodes (the root node is ) and asked them to do LCA queries on the tree (each query is in the form x y
, and its answer is the LCA of nodes and in the tree). Since he didn't have the funds to make proper test data for his trees, he generated them randomly with the following algorithm: for every node , he picked a uniform random integer in the range to be its parent node.
Angie is feeling very demotivated and doesn't want to do her work. Can you solve the queries for her?
Constraints
for all
Input Specification
The first line contains the integers and .
The second line contains integers , the parents of nodes respectively. Note that node does not have a parent as it's the root node of the tree.
The next lines each contain a query of the form x y
.
Output Specification
For each query, output its answer on a new line.
Sample Input
10 5
1 2 1 1 4 2 1 6 9
3 9
10 7
4 4
1 3
2 3
Sample Output
1
1
4
1
2
Explanation
The tree from the sample input:
Comments