Byteasar 设计了一台新架构的超级计算机。它可能包含许多（相同的）处理单元。每个处理单元在每个时间单位内可以执行一条指令。

该计算机的程序不是顺序执行的，而是具有树状结构。每条指令可能有零个、一个或多个后续指令，对于这些后续指令，该指令即为父指令。

程序中的指令可以在所有可用的处理单元上并行执行。此外，它们可以以多种顺序执行：唯一的限制是，除非其父指令已经执行完毕，否则该指令不能执行。例如，对于一条已经执行完毕的指令，其所有后续指令中，可以同时执行的指令数量最多为处理单元的数量。

Byteasar 有一个特定的程序需要运行。由于他喜欢优化资源利用，他想知道处理单元的数量会如何影响运行时间。他要求你针对给定的程序和处理单元数量，确定该程序在拥有这么多处理单元的超级计算机上的最短执行时间。

输入格式

标准输入的第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 1\,000\,000$)，由单个空格分隔，分别指定 Byteasar 程序中的指令数量和运行时间查询的数量（针对不同数量的处理单元）。

输入的第二行包含一个由 $q$ 个整数组成的序列 $k_{1}, k_{2}, \dots, k_{q}$ ($1 \le k_{i} \le 1\,000\,000$)，由单个空格分隔：$k_{i}$ 是 Byteasar 第 $i$ 次查询中的处理单元数量。

输入的第三行（最后一行）包含一个由 $n-1$ 个整数组成的序列 $a_{2}, a_{3}, \dots, a_{n}$ ($1 \le a_{i} < i$)，由单个空格分隔：$a_{i}$ 指定了编号为 $i$ 的指令的父指令编号。指令按从 $1$ 到 $n$ 的连续整数编号，其中编号为 $1$ 的指令是程序的首条指令。

在总分占比 $35\%$ 的测试中，满足 $n \le 30\,000$，$q \le 50$。此外，在其中占比 $20\%$ 的子任务中，额外满足 $n \le 1\,000$，$q \le 10$。

输出格式

你的程序应向标准输出打印一行，包含 $q$ 个由单个空格分隔的整数：其中第 $i$ 个数字应指定该程序在拥有 $k_{i}$ 个处理单元的超级计算机上的最短执行时间。

样例

输入 1

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

输出 1

8

说明

该程序可以按如下方式执行：

• 时间 1：指令 1
• 时间 2：指令 2 3 4
• 时间 3：指令 5 6 7
• 时间 4：指令 8 10
• 时间 5：指令 9 12
• 时间 6：指令 11 13 14
• 时间 7：指令 15 16 17
• 时间 8：指令 18 19 20

样例评测测试

• 1ocen: $n=10, q=2$，指令树是一条路径；
• 2ocen: $n=10, q=3$，一个小型的随机测试；
• 3ocen: $n=100, q=3$，除 $1$ 以外的所有指令都是其后续指令；
• 4ocen: $n=127, q=1$，指令构成一棵完全二叉树；
• 5ocen: $n=1,000,000, q=31$，指令树是一条长路径。