Background

Little Soup is looking through their family genealogy. Their family genealogy forms a tree. Little Soup noticed that, because so much time has passed, some branches of their family have already died out, and they are very curious about this.

Problem 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