Answer ancestor-walk queries on a rooted tree

## Problem (Tree / Parent Array Queries) You are given a rooted tree with **n** nodes labeled **1..n**, represented by a **parent array** `par[1..n]`: - `par[i]` is the parent of node `i` - `par[root] = -1` - The input guarantees this forms a valid rooted tree (exactly one root, no cycles). Example: - `par = [-1, 1, 1, 2, 2, 2, 2]` (meaning `par[1] = -1`, `par[2] = 1`, …) You will be given **q** queries. Each query provides: - a starting node `u` - an integer `k ≥ 0` (“number of commands/steps”) For each query, start at node `u` and **move to the parent** exactly `k` times (or until you reach the root). If you reach the root before using all steps, you remain at the root. ### Output For each query, output the label of the final node where you stop. ### Constraints (assume large input) Design an approach efficient for large `n, q` (e.g., up to 2e5).