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$ 个词时读出的字符数。

样例

输入格式 1

5
0 1 2 3 4
5

输出格式 1

0

说明

共有 $6$ 个单词，编号为 $0\dots 5$。单词 $5$ 是唯一不是其他单词前缀的词，所以词库只有它。一般来说，词库只剩一个词时，Elsie 不需要任何字符就能确定它。

输入格式 2

4
0 0 1 1
4
3
2

输出格式 2

2
1
0

说明

词库包含单词 $2$、$3$ 和 $4$。

Elsie 需要两个字符才能确定单词 $4$，因为单词 $3$ 和 $4$ 的首字符相同。

Bessie 读出单词 $3$ 的第一个字符后，Elsie 就能唯一确定它，因为单词 $4$ 已经被读过。

输入格式 3

4
0 0 1 1
2
3
4

输出格式 3

1
2
0

子任务

• 输入四至五：没有单词的长度超过 $20$。
• 输入六至十：词库中所有单词的长度之和不超过 $10^7$。
• 输入十一至十八：没有额外限制。

题目作者：Benjamin Qi