CSES - Company Queries I
  • Time limit: 1.00 s
  • Memory limit: 512 MB

A company has nn employees, who form a tree hierarchy where each employee has a boss, except for the general director.

Your task is to process qq queries of the form: who is employee xx's boss kk levels higher up in the hierarchy?

Input

The first input line has two integers nn and qq: the number of employees and queries. The employees are numbered 1,2,,n1,2,\dots,n, and employee 11 is the general director.

The next line has n1n-1 integers e2,e3,,ene_2,e_3,\dots,e_n: for each employee 2,3,,n2,3,\dots,n their boss.

Finally, there are qq lines describing the queries. Each line has two integers xx and kk: who is employee xx's boss kk levels higher up?

Output

Print the answer for each query. If such a boss does not exist, print 1-1.

Constraints

  • 1n,q21051 \le n,q \le 2 \cdot 10^5
  • 1eii11 \le e_i \le i-1
  • 1xn1 \le x \le n
  • 1kn1 \le k \le n

Example

Input:

5 3
1 1 3 3
4 1
4 2
4 3

Output:

3
1
-1