题目描述

Bajtazar 打造了一台设计新颖的超级计算机。它可配备多个相同处理器，每个处理器每单位时间执行一条指令。程序不再按顺序运行，而是呈树状结构。每条指令可能有零条、一条或多条后续指令。执行完一条指令后，其后续指令可按任意顺序执行，甚至在不同处理器上并行运行。若超级计算机有 $k$ 个处理器，每单位时间最多并行执行 $k$ 条指令。

Bajtazar 准备运行一个程序。他希望充分利用资源，思考处理器数量如何影响运行速度。请你编写程序，帮他计算给定程序和处理器数量下，最短的程序执行时间。

输入格式

输入第一行包含两个整数 $n, q$ $(1 \leq n, q \leq 1000000)$，分别表示程序的指令数和查询次数。

第二行包含 $q$ 个整数 $k_1, k_2, \ldots, k_q$ $(1 \leq k_i \leq 1000000)$，$k_i$ 表示第 $i$ 次查询的处理器数量。

第三行包含 $n-1$ 个整数 $a_2, a_3, \ldots, a_n$ $(1 \leq a_i < i)$，$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

程序执行过程如下表所示：

附加样例

• $n=10, q=2$，指令树为路径；
• $n=10, q=3$，小型随机测试；
• $n=100, q=3$，所有指令直接跟随指令 $1$；
• $n=127, q=1$，指令形成满二叉树；
• $n=1000000, q=31$，指令树为长路径。

数据范围与提示

对于 $35\%$ 的数据，$n \leq 30000, q \leq 50$。
对于其中 $20\%$ 的数据，$n \leq 1000, q \leq 10$。