Bessie помогает Elsie готовиться к проверке словарного запаса. Слова выбираются из банка из $M$ различных слов, ни одно из которых не является префиксом другого слова банка.

Пока банк не пуст, Bessie выбирает слово, удаляет его из банка и читает Elsie по одному символу слева направо. Elsie должна сообщить, как только сможет однозначно определить слово, после чего чтение прекращается.

Bessie уже решила читать в порядке $w_1,w_2,\dots,w_M$. Если Elsie отвечает максимально быстро, сколько символов каждого слова будет прочитано?

Слова даны в сжатом формате. Сначала определим $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$ укажите число прочитанных символов $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$.

Для определения слова $4$ нужны два символа, поскольку у слов $3$ и $4$ первый символ совпадает.

После первого символа слова $3$ Elsie однозначно определяет его, поскольку слово $4$ уже прочитано.

Входные данные 3

4
0 0 1 1
2
3
4

Выходные данные 3

1
2
0

Подзадачи

• Входы с четвёртого по пятый: длина каждого слова не больше $20$.
• Входы с шестого по десятый: сумма длин слов банка не превышает $10^7$.
• Входы с одиннадцатого по восемнадцатый: дополнительных ограничений нет.

Автор задачи: Benjamin Qi