Kings

Hundreds of years ago, the entire Europe and Asia (also known as Eurasia) was known as a single country and had a single king. Upon his death, his sons then divided the country into equal parts and each son became king and ruled his own kingdom. If a king had a single son, then the son would become king of the same country. It was also possible that a king died childless - his country would then be invaded and claimed by one of the other kings. This process went on until the continent was eventually split into the countries we know today - and the borders have stayed the same ever since. A historian has gathered a list of all kings that have ever ruled in a European or Asian country and wants to do some research. In order to better understand the whole family tree, he prepared a list of pairs of kings and wants you to help him identify the closest common progenitor of each pair.

Input data

There are a total of $n$ kings, and the historian has assigned a random unique number from $1$ to $n$ to each of them. His only guarantee is that $1$ was the first ever king of Eurasia. The first line contains integers $n$ and $m$, where $m$ is the number of queries the historian has. The next line has $n - 1$ integers, with the $i$th number representing the father of king $i + 1$ (since king $1$ was the first one, his father was not a king). Each of the next $m$ lines has a pair of integers $x$ and $y$, representing a query from the historian: what is the closest common progenitor of kings $x$ and $y$?

Output data

For each query, output the answer on a new line.

Constraints and clarifications

• $1 \leq n \leq 100 \ 000$
• $1 \leq m \leq 2 \ 000 \ 000$

Example 1

stdin

9 4
1 1 2 2 2 4 4 6
7 5
7 3
8 9
7 8

stdout

2
1
2
4