Беси помогает Эльзе играть со словами. Слова берутся из банка, содержащего
\(M\) различных слов, ни одно слово не является префиксом другого.
Пока банк не пустой, Беси выбирает слово из банка, удаляет его из банка,
читает его Эльзе по одному символу за раз слева направо. Задача Эльзы сказать
Беси, как только она уникально определит слово, после чего Беси прекращает
чтение.
Беси уже решила читать слова из словаря в порядке
\(w_1,w_2,\dots,w_M\). Если Эльза ответит так быстро, как это возможно, сколько
символов из каждого слова прочитает Беси?
Слова заданы в сжатом формате. Сначала мы определяем \(N+1\) (\(1\le N\le 10^6\))
различных слов и затем банк слов состоит из всех этих слов, ни одно из которых
не является префиксом другого. Слова определяются следующим образом:
- Изначально, 0-ое слово - пустая строка.
- Затем для каждого each \(1\le i\le N\), \(i\)-ое слово будет равно \(p_i\)-ому слову
плюс дополнительный символ в конце (\(0\le p_i<i\)). Символы выбираются так,
что все \(N+1\) слов различны.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(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\)-ым прочитанным. Гарантируется, что слова к чтению формируют перестановку
слов из банка.
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите \(M\) строк, где \(i\)-ая строка содержит количество символов \(i\)-го слова,
которое прочиает Беси.
Ваш ответ: