Parallel Tree Traversal on a Supercomputer

Byteasar has designed a supercomputer of novel architecture. The machine consists of many identical processing units, each capable of executing a single instruction per time unit. Programs for this computer are not sequential; instead, they form a tree structure. An instruction may have zero, one, or multiple subsequent instructions (its children), and an instruction can only be executed after its parent has been executed.

In one operation, you may choose to execute at most K unvisited instructions whose parent instructions have already been executed. Initially, only the root instruction (node 1) is considered executed. Given a rooted tree with N nodes (with node 1 as the root) and Q queries, each query provides an integer K. Your task is to determine the minimum number of operations required to traverse (i.e. execute) the entire tree.

Formally, you are given a rooted tree with N nodes. The tree is provided by specifying for each node i (2 ≤ i ≤ N) the index of its parent p_i (1 ≤ p_i < i). In each operation, you may choose at most K unvisited nodes, each of which has its parent visited in some previous operation. Compute and output the minimum number of operations needed to traverse all nodes for every query.

inputFormat

The input begins with a line containing two integers N and Q (the number of nodes and the number of queries respectively).

The second line contains N-1 integers: p₂, p₃, ..., p_N, where p_i denotes the parent of node i (1 ≤ p_i < i).

Then follow Q lines, each containing a single integer K.

outputFormat

For each query, output one integer representing the minimum number of operations required to traverse the entire tree.

sample

3 2
1 1
1
2

2
1