# K'th Ancestor

medium

You are given a tree of n nodes numbered from 0 to n-1 and is rooted at 0. You are given an array parent of length n where parent[i] denotes parent of i'th node (in case of root it's parent is itself). Now you have to answer q queries of format: a k answer to this query is k'th ancistor of node a if k'th ancistor does not exist simply print root. In simple words you have to find k'th ancistor of a node. Task: could u do it in log(n) or better time complexity.

## Constraints

1. 2 <= n <= 10^5 2. parent[0] = 0 3. 1 <= q <= 10^5 4. 0 <= a <= n-1 5. 1 <= k <= n

## Format

### Input

n p1 p2 p3 ... n numbers till pn q a1 k1 a2 k2 ... q queries till a(q) k(q)

### Output

for each query print in single line value of k'th ancistor

## Example

Sample Input

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

### Sample Output

2
1
0
0
0
3