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.
Input Format
n p1 p2 p3 ... n numbers till pn q a1 k1 a2 k2 ... q queries till a(q) k(q)
Output Format
for each query print in single line value of k'th ancistor
Constraints
1. 2 <= n <= 10^5 2. parent[0] = 0 3. 1 <= q <= 10^5 4. 0 <= a <= n-1 5. 1 <= k <= n
Notice
Try First, Check Solution later
1. You should first read the question and watch the question video.2. Think of a solution approach, then try and submit the question on editor tab.3. We strongly advise you to watch the solution video for prescribed approach.Example
Input
7 0 0 0 1 3 2 3 6 5 1 6 2 3 2 3 3 6 3 4 1
Output
2 1 0 0 0 3