Time limit: 0.75s Memory limit: 64MB Input: Output:

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 nn kings, and the historian has assigned a random unique number from 11 to nn to each of them. His only guarantee is that 11 was the first ever king of Eurasia. The first line contains integers nn and mm, where mm is the number of queries the historian has. The next line has n1n - 1 integers, with the iith number representing the father of king i+1i + 1 (since king 11 was the first one, his father was not a king). Each of the next mm lines has a pair of integers xx and yy, representing a query from the historian: what is the closest common progenitor of kings xx and yy?

Output data

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

Constraints and clarifications

  • 1n100 0001 \leq n \leq 100 \ 000
  • 1m2 000 0001 \leq m \leq 2 \ 000 \ 000

Example 1


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



Log in or sign up to be able to send submissions!