Условие:
Поликарпу на Новый Год подарили корневое дерево, где у каждой вершины есть своя буква. А ещё у Поликарпа есть любимое слово $s$. Страйк - это некоторый путь вниз по дереву (все рёбра в нём ведут от корня к листьям) такой, что в i-й вершине пути стоит буква s[i%len(s)]. Будем называть красотой вершины дерева максимальную длину страйка, который заканчивается в этой вершине. Помогите Поликарпу определить красоту каждой вершины в подаренном дереве.
Формат ввода
В первой строке дана строка $s$ ($1 \le |s| \le 10^4$).
Во второй строке дано число $N$ ($1 \le N \le 10^5$) - количество вершин в корневом дереве.
Далее в $N$ строках даны описания вершин дерева. В $i$-й ($0 \le i \le N-1$) строке дана буква $c_i$ и предок вершины в дереве $p_i$ ($0 \le p_i \le N-1$).
Вершина, у которой предок $p_i$ равен -1, является корнем дерева.
Все строки и буквы на вершинах состоят только из строчных букв латинского алфавита.
Формат вывода
В единственной строке через пробел выведите $N$ чисел - значение красоты для $i$-й вершины для $i$ от $0$ до $N-1$
