Chain of Command (Tree DFS Order, k-th Receiver)

You are given a tree rooted at 0, with parent[0]=-1. A notification sent to node p propagates in preorder DFS order, and the children of each node are visited in ascending order of number. Each query (p,k) returns the k-th node in the preorder sequence of p's subtree (1-based, including p); if k exceeds the subtree size, return -1.

This site adds the standard input/output protocol.

输入格式

n; one line of n parent values; q; then q lines of p k. Node numbers and p in queries are 0-based. By convention parent[0]=-1, and the parent array represents a valid tree rooted at 0. This site adds n≤200000, q≤200000.

输出格式

Output the answers in query order, separated by spaces.

样例 1

输入：

9
-1 0 0 1 1 1 2 6 7
4
0 4
1 3
5 1
6 2

输出：

4 4 5 7

样例 2

输入：

1
-1
2
0 1
0 2

输出：

0 -1

样例 3

输入：

5
-1 0 0 1 1
3
0 3
1 2
2 2

输出：

3 3 -1