- Time limit: 1.00 s
- Memory limit: 512 MB
A company has employees, who form a tree hierarchy where each employee has a boss, except for the general director.
Your task is to process queries of the form: who is employee 's boss levels higher up in the hierarchy?
Input
The first input line has two integers and : the number of employees and queries. The employees are numbered , and employee is the general director.
The next line has integers : for each employee their boss.
Finally, there are lines describing the queries. Each line has two integers and : who is employee 's boss levels higher up?
Output
Print the answer for each query. If such a boss does not exist, print .
Constraints
Example
Input:
5 3 1 1 3 3 4 1 4 2 4 3
Output:
3 1 -1