题目描述

Byteasar 设计了一种新型架构的超级计算机。

这台超级计算机可以包含许多个完全相同的处理单元。每个处理单元在一个单位时间内可以执行一条指令。

这台计算机上运行的程序并不是顺序结构，而是一棵有根树。每条指令对应树上的一个节点。一条指令可以有零条、一条或多条后续指令，这些后续指令在树中是它的子节点。

程序中的指令可以在所有可用处理单元上并行执行，并且执行顺序并不唯一。唯一的限制是：一条指令只有在它的父指令已经在之前的某个单位时间内执行完成后，才可以被执行。根节点对应的指令没有父指令，可以在第一个单位时间内执行。

换句话说，给定一棵 $n$ 个节点的有根树，根节点为 $1$。若超级计算机有 $k$ 个处理单元，则每个单位时间内至多可以选择 $k$ 个尚未执行的节点执行，且这些节点的父节点必须已经在之前的单位时间内执行完成。特别地，节点 $1$ 可以在第一个单位时间内执行。

Byteasar 想知道处理单元数量对程序运行时间的影响。对于每次询问给出的处理单元数量 $k_i$，请你求出执行完整个程序所需的最少单位时间数。

输入格式

第一行包含两个整数 $n,q$，分别表示程序中的指令数和询问数。

第二行包含 $q$ 个整数 $k_1,k_2,\ldots,k_q$，其中 $k_i$ 表示第 $i$ 次询问中超级计算机的处理单元数量。

第三行包含 $n-1$ 个整数 $a_2,a_3,\ldots,a_n$，其中 $a_i$ 表示编号为 $i$ 的指令的父指令编号。

指令编号为 $1$ 到 $n$，其中编号为 $1$ 的指令是程序的第一条指令，即树的根节点。

输出格式

输出一行，包含 $q$ 个整数，相邻两个整数之间用一个空格隔开。

第 $i$ 个整数表示当超级计算机有 $k_i$ 个处理单元时，执行完整个程序所需的最少单位时间数。

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

8

提示

样例解释

在样例中，超级计算机有 $3$ 个处理单元。

一种最优执行方案如下：

• 第 $1$ 个单位时间：执行节点 $1$。
• 第 $2$ 个单位时间：执行节点 $2,3,4$。
• 第 $3$ 个单位时间：执行节点 $5,7,8$。
• 第 $4$ 个单位时间：执行节点 $6,9$。
• 第 $5$ 个单位时间：执行节点 $10,11$。
• 第 $6$ 个单位时间：执行节点 $12,16,17$。
• 第 $7$ 个单位时间：执行节点 $13,18,19$。
• 第 $8$ 个单位时间：执行节点 $14,15,20$。

因此最少需要 $8$ 个单位时间。

数据范围

对于全部测试数据，满足：

$1 \le n,q \le 10^6$，

$1 \le k_i \le 10^6$，

$1 \le a_i < i$。