1006_E. Military Problem
In this problem you will have to help Berland army with organizing their command delivery system.

There are n officers in Berland army. The first officer is the commander of the army, and he does not have any superiors. Every other officer has exactly one direct superior. If officer a is the direct superior of officer b, then we also can say that officer b is a direct subordinate of officer a.

Officer x is considered to be a subordinate (direct or indirect) of officer y if one of the following conditions holds:

  * officer y is the direct superior of officer x; 
  * the direct superior of officer x is a subordinate of officer y. 



For example, on the picture below the subordinates of the officer 3 are: 5, 6, 7, 8, 9.

The structure of Berland army is organized in such a way that every officer, except for the commander, is a subordinate of the commander of the army.

Formally, let's represent Berland army as a tree consisting of n vertices, in which vertex u corresponds to officer u. The parent of vertex u corresponds to the direct superior of officer u. The root (which has index 1) corresponds to the commander of the army.

Berland War Ministry has ordered you to give answers on q queries, the i-th query is given as (u_i, k_i), where u_i is some officer, and k_i is a positive integer.

To process the i-th query imagine how a command from u_i spreads to the subordinates of u_i. Typical DFS (depth first search) algorithm is used here.

Suppose the current officer is a and he spreads a command. Officer a chooses b — one of his direct subordinates (i.e. a child in the tree) who has not received this command yet. If there are many such direct subordinates, then a chooses the one having minimal index. Officer a gives a command to officer b. Afterwards, b uses exactly the same algorithm to spread the command to its subtree. After b finishes spreading the command, officer a chooses the next direct subordinate again (using the same strategy). When officer a cannot choose any direct subordinate who still hasn't received this command, officer a finishes spreading the command.

Let's look at the following example:

<image>

If officer 1 spreads a command, officers receive it in the following order: [1, 2, 3, 5 ,6, 8, 7, 9, 4].

If officer 3 spreads a command, officers receive it in the following order: [3, 5, 6, 8, 7, 9].

If officer 7 spreads a command, officers receive it in the following order: [7, 9].

If officer 9 spreads a command, officers receive it in the following order: [9].

To answer the i-th query (u_i, k_i), construct a sequence which describes the order in which officers will receive the command if the u_i-th officer spreads it. Return the k_i-th element of the constructed list or -1 if there are fewer than k_i elements in it.

You should process queries independently. A query doesn't affect the following queries.

Input

The first line of the input contains two integers n and q (2 ≤ n ≤ 2 ⋅ 10^5, 1 ≤ q ≤ 2 ⋅ 10^5) — the number of officers in Berland army and the number of queries.

The second line of the input contains n - 1 integers p_2, p_3, ..., p_n (1 ≤ p_i < i), where p_i is the index of the direct superior of the officer having the index i. The commander has index 1 and doesn't have any superiors.

The next q lines describe the queries. The i-th query is given as a pair (u_i, k_i) (1 ≤ u_i, k_i ≤ n), where u_i is the index of the officer which starts spreading a command, and k_i is the index of the required officer in the command spreading sequence.

Output

Print q numbers, where the i-th number is the officer at the position k_i in the list which describes the order in which officers will receive the command if it starts spreading from officer u_i. Print "-1" if the number of officers which receive the command is less than k_i.

You should process queries independently. They do not affect each other.

Example

Input

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


Output

3
6
8
-1
9
4
```python
"""
    Satwik_Tiwari ;) .
    30th july , 2020  - Thursday
"""

#===============================================================================================
#importing some useful libraries.
from __future__ import division, print_function

from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase

from itertools import *
import bisect
from heapq import *
from math import *
from copy import *
from collections import deque
from collections import Counter as counter  # Counter(list)  return a dict with {key: count}
from itertools import combinations as comb # if a = [1,2,3] then print(list(comb(a,2))) -----> [(1, 2), (1, 3), (2, 3)]
from itertools import permutations as permutate
from bisect import bisect_left as bl
#If the element is already present in the list,
# the left most position where element has to be inserted is returned.
from bisect import bisect_right as br
from bisect import bisect
#If the element is already present in the list,
# the right most position where element has to be inserted is returned

#==============================================================================================
#fast I/O region
BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")

#===============================================================================================
### START ITERATE RECURSION ###
from types import GeneratorType
def iterative(f, stack=[]):
  def wrapped_func(*args, **kwargs):
    if stack: return f(*args, **kwargs)
    to = f(*args, **kwargs)
    while True:
      if type(to) is GeneratorType:
        stack.append(to)
        to = next(to)
        continue
      stack.pop()
      if not stack: break
      to = stack[-1].send(to)
    return to
  return wrapped_func
#### END ITERATE RECURSION ####

#===============================================================================================
#some shortcuts

mod = 1000000007
def inp(): return sys.stdin.readline().rstrip("\r\n") #for fast input
def out(var): sys.stdout.write(str(var))  #for fast output, always take string
def lis(): return list(map(int, inp().split()))
def stringlis(): return list(map(str, inp().split()))
def sep(): return map(int, inp().split())
def strsep(): return map(str, inp().split())
# def graph(vertex): return [[] for i in range(0,vertex+1)]
def zerolist(n): return [0]*n
def nextline(): out("\n")  #as stdout.write always print sring.
def testcase(t):
    for p in range(t):
        solve()
def printlist(a) :
    for p in range(0,len(a)):
        out(str(a[p]) + ' ')
def lcm(a,b): return (a*b)//gcd(a,b)
def power(a,b):
    ans = 1
    while(b>0):
        if(b%2==1):
            ans*=a
        a*=a
        b//=2
    return ans
def ncr(n,r): return factorial(n)//(factorial(r)*factorial(max(n-r,1)))
def isPrime(n) :
    if (n <= 1) : return False
    if (n <= 3) : return True
    if (n % 2 == 0 or n % 3 == 0) : return False
    i = 5
    while(i * i <= n) :
        if (n % i == 0 or n % (i + 2) == 0) :
            return False
        i = i + 6
    return True

#===============================================================================================
# code here ;))
cnt = [0]
@iterative
def dfs(v,visited,st,new,stime,endtime):
    new.append(st)
    visited[st] = 1
    stime[st] = cnt[0]
    cnt[0]+=1

    for i in v[st]:
        if(visited[i] == 0):
            ok = yield dfs(v,visited,i,new,stime,endtime)

    endtime[st] = cnt[0]
    cnt[0]+=1
    yield True

def solve():
    n,q = sep()
    p = lis()
    graph = [[] for i in range(n)]
    for i in range(0,n-1):
        a,b = i+1,p[i]-1
        graph[a].append(b)
        graph[b].append(a)

    for i in range(n):
        graph[i] = sorted(graph[i])

    sttime = [0]*(n)
    endtime = [0]*(n)
    new = []
    vis = [0]*(n)
    dfs(graph,vis,0,new,sttime,endtime)

    # print(new)
    # print(sttime)
    # print(endtime)
    pos = [0]*n

    for i in range(n):
        pos[new[i]] = i
    # print(pos)
    for i in range(q):
        a,k = sep()
        a-=1
        ind = pos[a]
        to = ind+k-1
        # print(new[to],ind,to)
        if(to<n and (sttime[new[to]])>=sttime[a] and endtime[new[to]]<=endtime[a]):
            print(new[to]+1)
        else:
            print(-1)





testcase(1)
# testcase(int(inp()))













```