Supercomputer

Time limit2sMemory limit256 MB

Summary

Given a rooted tree of unit-time tasks and many processor counts, compute the fastest finishing time for each count.

Level: Hard8 of 10
Topics: Tree, Prefix sum, Math, Greedy
Solved: No attempts yet

Problem

Byteasar designed a supercomputer with many identical processing units. Each unit runs one instruction per time unit.

The program is a tree, not a sequence. Each instruction has zero or more children, and must finish before any of its children can start. Among ready children, up to as many as there are processing units may run in parallel.

For each query $k$ , find the minimum time to finish every instruction.

Input

Line 1: integers $n$ and $q$ ( $1 \leq n, q \leq 1{,}000{,}000$ )
Line 2: $q$ integers $k_1, \ldots, k_q$ ( $1 \leq k_i \leq 1{,}000{,}000$ )
Line 3: $a_2, \ldots, a_n$ ( $1 \leq a_i < i$ ), the parent of instruction $i$ . Instruction 1 is the root.

Output

Print $q$ integers on one line: the minimum execution time for each $k_i$ .

Hint

See the figure in the Korean statement for the sample tree layout. Precompute how many nodes lie at each depth, then for each $k$ maximize $j + \lceil s_{j+1} / k \rceil$ over depth thresholds $j$ .

Examples3

Example 1

Input

20 1
3
1 1 1 3 4 3 2 8 6 9 10 12 12 13 14 11 11 11 11

Expected output

Example 2
Input
```
10 2
1
10
1 1 1 1 1 1 1 1 1
```
Expected output
```
10 2
```
Example 3
Input
```
7 3
1
2
7
1 1 2 2 3 3
```
Expected output
```
7 4 3
```