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?
~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~
The first line contains the integers ~N~ and ~Q~.
The second line contains ~N-1~ integers ~p_2, p_3, \ldots, p_N~, the parents of nodes ~2, 3, \ldots, 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
For each query, output its answer on a new line.
10 5 1 2 1 1 4 2 1 6 9 3 9 10 7 4 4 1 3 2 3
1 1 4 1 2
The tree from the sample input: