Description

Little Soup gives you their family genealogy tree and wants to ask: in this tree, who is the $\text{lowest common ancestor}$ of all children on level $k$ (i.e., all nodes whose depth is $k$; the root has depth $1$, and the root index is $1$).

Input Format

The first line contains two integers $n, m$.
The second line contains $n$ integers, where the $i$-th integer is $f_i$, meaning the parent of $i$ is $f_i$. Note that $f_1$ is fixed to be $0$.
Then follow $m$ lines, each containing one integer $k$, representing Little Soup's query.

Output Format

For each query from Little Soup, output one integer, which is the $\text{lowest common ancestor}$ of all nodes with depth $k$.

8 3
0 1 1 2 2 3 4 5
2
1
4

1
1
2

11 4
0 1 1 3 3 3 4 5 8 8 10
3
4
5
6

3
3
8
11

Hint

Sample Explanation 1:

Sample Explanation 2:

It is guaranteed that there exists at least one node with depth $k$.

$\begin{array}{|c|c|c|}\hline \text{Testdata ID} & n, m & \text{Special Property} \\\hline 1 & \le 10 & \diagdown \\\hline 2 & \le 100 & \diagdown \\\hline 3 \sim 4 & \le 10^3 & \diagdown \\\hline 5 & \le 3 \times 10^5 & \text{The tree is a single chain} \\\hline 6 & \le 3 \times 10^5 & \diagdown \\\hline 7 \sim 10 & \le 3 \times 10^6 & \diagdown \\\hline 11 \sim 12 & \le 5 \times 10^6 & \diagdown \\\hline \end{array}$

For $100\%$ of the testdata, $n \le 5 \times 10^6$, and $m \le n$.

Friendly reminder: this problem is quite strict on constant factors. Please pay attention to the impact of large constants and time/memory complexity. If you get stuck due to constant-factor limits, you can try using fast input.

Translated by ChatGPT 5