题目描述

Bessie 正在帮助 Elsie 准备她即将到来的词汇测验。要测验的单词将从 $M$ 个不同单词的词库中抽取，其中词库里没有一个单词是另一个单词的前缀。

当词库非空时，Bessie 将从词库中选择一个单词，将其从词库中移除，并从左到右逐个字符地读给 Elsie。Elsie 的任务是在她能够唯一确定该单词时告诉 Bessie，此后 Bessie 将停止朗读。

Bessie 已经决定按顺序 $w_1,w_2,\dots,w_M$ 朗读单词。如果 Elsie 尽可能快地回答，Bessie 将朗读每个单词的多少个字符？

这些单词以一种压缩格式给出。我们将首先定义 $N+1$（$1\le N\le 10^6$）个不同的单词，然后词库将由其中所有不作为另一个单词前缀的单词组成。这些单词定义如下：

• 初始时，第 $0$ 个单词为空字符串。
• 然后对于每一个 $1\le i\le N$，第 $i$ 个单词将等于第 $p_i$ 个单词在末尾加上一个额外的字符（$0\le p_i<i$）。字符的选择使得所有 $N+1$ 个单词各不相同。

输入格式

输入的第一行包含 $N$，其中 $N+1$ 是以压缩格式给出的单词的数量。

以下一行包含 $p_1,p_2,\dots,p_N$，其中 $p_i$ 表示第 $i$ 个单词是通过取第 $p_i$ 个单词并在末尾添加一个字符形成的。

令 $M$ 为不是某个其他单词前缀的单词数量。以下 $M$ 行将包含 $w_1,w_2,\dots,w_M$，表示第 $w_i$ 个单词将是第 $i$ 个被朗读的单词。输入保证朗读的单词形成词库中单词的一个排列。

输出格式

输出 $M$ 行，其中第 $i$ 行包含 Bessie 对第 $i$ 个单词朗读的字符数量。

5
0 1 2 3 4
5

0

4
0 0 1 1
4
3
2

2
1
0

4
0 0 1 1
2
3
4

1
2
0

提示

样例 1 解释：

有 $6$ 个单词编号为 $0 \dots 5$。单词 $5$ 是唯一一个不是另一个单词的前缀的单词，因此它是词库中唯一的单词。一般地说，一旦库中仅剩下一个单词，Elsie 就不再需要任何字符以确定它。

样例 2 解释：

词库由单词 $2$，$3$ 和 $4$ 组成。

Elsie 需要两个字符来确定单词 $4$，因为单词 $3$ 和 $4$ 的第一个字符相同。

一旦 Bessie 朗读了单词 $3$ 的第一个字符，Elsie 就有了足够的字符来唯一确定它，因为单词 $4$ 已经被朗读。

• 测试点 $4\sim 5$：所有单词的长度均不超过 $20$。
• 测试点 $6\sim 10$：词库中所有单词的长度之和不超过 $10^7$。
• 测试点 $11\sim 18$：没有额外限制。