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: