31603번 - Tree Quiz 다국어

문제

Your friend wants to quiz you. You are given a rooted tree with $n$ nodes, numbered from 1ドル$ to $n$. For every node $i,ドル its parent is node $p_i,ドル except for the root (the node without a parent) which has $p_i = 0$. Node $u$ is an ancestor of node $v$ if either $u = v,ドル or node $u$ is an ancestor of the parent of node $v$ (if it exists).

We say that node $z$ is a common ancestor of nodes $x$ and $y$ if node $z$ is an ancestor of both nodes $x$ and $y$. We say that node $z$ is the lowest common ancestor of nodes $x$ and $y$ if it is a common ancestor of nodes $x$ and $y,ドル and every common ancestor of nodes $x$ and $y$ is also an ancestor of node $z$. We denote the lowest common ancestor of nodes $x$ and $y$ by $LCA(x, y)$. In particular, $LCA(x, x) = x$.

Your friend would like to run the following pseudocode:

let L be an empty array
for x = 1 to n
 for y = 1 to n
 append ((x - 1) * n * n + (LCA(x, y) - 1) * n + (y - 1)) to L
sort L in non-decreasing order

Your friend has $q$ questions, numbered from 1ドル$ to $q$. In question $j,ドル you are given an integer $k_j$ and asked to find the $k_j$-th element of the array $L$. Note that $L$ is 1ドル$-indexed, so the indices range from 1ドル$ to $n^2,ドル inclusive. To pass the quiz, you have to answer all of the questions.

입력

The first line of input contains two integers $n$ and $q$ (1ドル ≤ n ≤ 100,円 000$; 1ドル ≤ q ≤ 100,円 000$). The second line contains $n$ integers $p_1, p_2, \dots , p_n$ (0ドル ≤ p_i ≤ n$ for all $i$). It is guaranteed that the given values represent a rooted tree. Each of the next $q$ lines contains an integer. The $j$-th line contains $k_j$ (1ドル ≤ k_j ≤ n^2$).

출력

For each question in order, output an integer representing the answer to the question.

제한

힌트