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:

$\text{[math]}$

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 \le n \le 2 \cdot 10^5, 1 \le q \le 2 \cdot 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, \dots, p_n$$$ ($$$1 \le p_i \lt 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 \le u_i, k_i \le 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.

Idx	Name	Rating
A	Adjacent Replacements	800
B	Polycarp's Practice	1200
C	Three Parts of the Array	1200
D	Two Strings Swaps	1700
E	Military Problem	1600
F	Xor-Paths	2100

Codeforces Round 498 (Div. 3)