Autocompletion

Description:

Input:

The first line contains one integer $$$n$$$ ($$$1 \le n \le 10^6$$$).

Then $$$n$$$ lines follow, the $$$i$$$-th line contains one integer $$$p_i$$$ ($$$0 \le p_i < i$$$) and one lowercase Latin character $$$c_i$$$. These lines form some set of strings such that $$$S$$$ is its subset as follows: there are $$$n + 1$$$ strings, numbered from $$$0$$$ to $$$n$$$; the $$$0$$$-th string is an empty string, and the $$$i$$$-th string ($$$i \ge 1$$$) is the result of appending the character $$$c_i$$$ to the string $$$p_i$$$. It is guaranteed that all these strings are distinct.

The next line contains one integer $$$k$$$ ($$$1 \le k \le n$$$) — the number of strings in $$$S$$$.

The last line contains $$$k$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_k$$$ ($$$1 \le a_i \le n$$$, all $$$a_i$$$ are pairwise distinct) denoting the indices of the strings generated by above-mentioned process that form the set $$$S$$$ — formally, if we denote the $$$i$$$-th generated string as $$$s_i$$$, then $$$S = {s_{a_1}, s_{a_2}, \dots, s_{a_k}}$$$.

Output:

Print $$$k$$$ integers, the $$$i$$$-th of them should be equal to the minimum number of seconds required to type the string $$$s_{a_i}$$$.

Sample Input:

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

Sample Output:

2 4 1 3 3 

Sample Input:

8
0 a
1 b
2 a
2 b
4 a
4 b
5 c
6 d
5
2 3 4 7 8

Sample Output:

1 2 2 4 4 

Note:

In the first example, $$$S$$$ consists of the following strings: ieh, iqgp, i, iqge, ier.