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 $N$ nodes (the root node is $1$) and asked them to do $Q$ LCA queries on the tree (each query is in the form x y, and its answer is the LCA of nodes $x$ and $y$ 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 $i$ $(2\le i\le N)$, he picked a uniform random integer in the range $[1,i)$ 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

$2\le x,y\le N\le 6\times {10}^6$

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

$1\le p_i<i$ for all $2\le i\le N$

Input Specification

The first line contains the integers $N$ and $Q$.

The second line contains $N-1$ integers $p_2,p_3,\dots ,p_N$, the parents of nodes $2,3,\dots ,N$ respectively. Note that node $1$ does not have a parent as it's the root node of the tree.

The next $Q$ 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: