给你一组字符串$$$S$$$。每个字符串均由小写拉丁字母组成。
对于该集合中的每个字符串,您想要计算键入该字符串所需的最小秒数。要输入字符串,您必须从空字符串开始,然后使用以下操作将其转换为您要输入的字符串:
- 如果当前字符串是$$$t$$$,则选择一些小写拉丁字母$$$c$$$并将其附加到$$$t$$$后面,因此当前字符串变为$$$t + c$$$。此操作需要 $$$1$$$ 秒;
- 使用自动完成功能。当您尝试自动完成当前字符串 $$$t$$$ 时,将显示 S$$$ 中所有字符串 $$$s \ 的列表,其中 $$$t$$$ 是 $$$s$$$ 的前缀。如果 $$$t$$$ 是来自 $$$S$$$ 的字符串,并且字符串按字典顺序排序,则此列表包括 $$$t$$$ 本身。您可以在 $$$i$$$ 秒内将 $$$t$$$ 转换为该列表中的第 $$$i$$$ 字符串。请注意,您可以从此列表中选择您想要的任何字符串,它不一定是您尝试输入的字符串。
输入 $$$S$$$ 中的每个字符串至少需要花费多少秒?
请注意,$$$S$$$ 中的字符串是以一种不寻常的方式给出的。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^6$$$)。
接下来是 $$$n$$$ 行,第 $$$i$$$ 行包含一个整数 $$$p_i$$$ ($$$0 \le p_i < i$$$) 和一个小写拉丁字符 $$$c_i$$$。这些行形成了一些字符串集合,$$$S$$$ 是其子集,如下所示:有 $$$n + 1$$$ 字符串,编号从 $$$0$$$ 到 $$$n$$$;第 $$$0$$$ 字符串是空字符串,第 $$$i$$$ 字符串 ($$$i \ge 1$$$) 是将字符 $$$c_i$$$ 附加到字符串 $$$p_i$$$ 的结果。保证所有这些字符串都是不同的。
下一行包含一个整数 $$$k$$$ ($$$1 \le k \le n$$$) — $$$S$$$ 中的字符串数量。
最后一行包含 $$$k$$$ 整数 $$$a_1$$$, $$$a_2$$$, ..., $$$a_k$$$ ($$$1 \le a_i \le n$$$, 所有 $$$a_i$$$ 都是成对不同的) 表示由上述过程生成的形成集合 $$$S$$$ 的字符串的索引 - 正式地,如果我们将第 $$$i$$$ 生成的字符串表示为 $$$s_i$$$,则 $$$S = {s_{a_1}, s_{a_2}, \dots, s_{a_k}}$$$。
输出
打印 $$$k$$$ 个整数,其中第 $$$i$$$ 应等于键入字符串 $$$s_{a_i}$$$ 所需的最小秒数。
示例
输入 #1
10 0 i 1 q 2 g 0 k 1 e 5 r 4 m 5 h 3 p 3 e 5 8 9 1 10 6
输出 #1
2 4 1 3 3
输入 #2
8 0 a 1 b 2 a 2 b 4 a 4 b 5 c 6 d 5 2 3 4 7 8
输出 #2
1 2 2 4 4
注意
在第一个示例中,$$$S$$$ 由以下字符串组成:ieh、iqgp、i、iqge、ier。