G. Автодополнение
ограничение по времени на тест
7 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть множество строк $$$S$$$. Каждая строка состоит из строчных букв латинского алфавита.

Для каждой строки вы хотите посчитать, сколько секунд потребуется, чтобы набрать ее в вашем текстовом редакторе. Чтобы набрать строку, вам нужно начать с пустой строки и преобразовать ее в ту строку, которую вы хотите набрать, при помощи следующих операций:

  • для текущей строки $$$t$$$ можно выбрать любую строчную латинскую букву $$$c$$$ и приписать ее $$$t$$$, после чего текущая строка станет $$$t + c$$$. Это действие требует $$$1$$$ секунду;
  • использовать автодополнение. При использовании автодополнения с текущей строкой $$$t$$$ вам показывается список всех таких строк $$$s \in S$$$, что $$$t$$$ — префикс $$$s$$$. Этот список включает саму строку $$$t$$$, если $$$t$$$ принадлежит $$$S$$$, и строки в нем расположены в лексикографическом порядке. Вы можете превратить $$$t$$$ в $$$i$$$-ю строку из этого списка за $$$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}$$$.

Примеры
Входные данные
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
Выходные данные
2 4 1 3 3
Входные данные
8
0 a
1 b
2 a
2 b
4 a
4 b
5 c
6 d
5
2 3 4 7 8
Выходные данные
1 2 2 4 4
Примечание

В первом примере $$$S$$$ состоит из следующих строк: ieh, iqgp, i, iqge, ier.