D. Анаграммные пути
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У жабы Ильи есть подвешенное двоичное дерево с корнем в вершине $$$1$$$. Деревом называется связный граф без циклов. Дерево называется подвешенным, если в нем выделена одна вершина, эта вершина называется корнем. Вершина $$$u$$$ является сыном вершины $$$v$$$, если $$$u$$$ и $$$v$$$ соединены ребром, и $$$v$$$ ближе к корню, чем $$$u$$$. Листом называется вершина, которая не является корнем, и у которой нет детей.

В дереве Ильи у каждой вершины не более двух детей, и на каждом ребре записан символ. Каждый символ может быть строчной буквой латинского алфавита или знаком вопроса '?'.

Илья немного изменит дерево $$$q$$$ раз. Каждое обновление заменит один символ на ровно одном ребре. После каждого обновления Илья должен проверить, является ли дерево анаграммным и если это так, то еще и найти его анаграмность для каждой буквы. Это непросто объяснить, но мы попробуем.

Для начала, строка $$$a$$$ является анаграммой строки $$$b$$$, если возможно переставить буквы строки $$$a$$$ (не меняя сами буквы) так, что она станет равной строке $$$b$$$. Например, строка «fortyfive» является анаграммой строки «overfifty», но строка «aabb» — не анаграмма строки «bbba».

Рассмотрим путь от корня до листа. Символы на этом пути образуют строку, скажем, что эта строка ассоциирована с этим листом. Дерево называется анаграммным, если и только если возможно заменить каждый знак вопроса на строчную букву латинского алфавита так, что для любой пары листьев ассоциированные строки этих листьев являются анаграммами друг друга.

Если дерево анаграммное, тогда его анаграмность для буквы $$$c$$$ равна максимальному возможному количеству букв $$$c$$$ в строке, ассоциированной с некоторым листом, после корректной замены всех знаков вопроса.

После каждого обновления проверьте, является ли дерево анаграммным, и если является, то найдите $$$\sum{f(c) \cdot ind(c)}$$$ по всем буквам $$$c$$$, где $$$f(c)$$$ — это анаграмность для буквы $$$c$$$, а $$$ind(x)$$$ — порядок буквы в алфавите ($$$ind($$$"a"$$$) = 1$$$, $$$ind($$$"b"$$$) = 2$$$, ..., $$$ind($$$"z"$$$) = 26$$$).

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

В первой строке записано два целых числа $$$n$$$ и $$$q$$$ ($$$2 \leq n \leq 150\,000$$$, $$$1 \leq q \leq 150\,000$$$) — количество вершин в дереве и количество запросов.

В следующих $$$n-1$$$ строках записано по одному целому числу и по одному символу. В $$$i$$$-й из них записано целое число $$$p_i$$$ и символ $$$c_i$$$ ($$$1 \leq p_i \leq i$$$, $$$c_i$$$ это строчный символ латинского алфавита или знак вопроса '?'), описывающих ребро между вершинами $$$p_i$$$ и $$$i+1$$$ с символом $$$c_i$$$, записанным на нем.

Корень этого дерева это вершина $$$1$$$, и у каждой вершины есть не более двух детей.

В следующих $$$q$$$ строк записано по одному целому числу и по одному символу, описывающих запросы. В $$$i$$$-й из них записано по два целых числа $$$v$$$ и $$$c$$$ ($$$2 \leq v \leq n$$$, $$$c$$$ это строчный символ латинского алфавита или знак вопроса '?'), описывающих, что обновленный символ на ребре между вершинами $$$p_{v-1}$$$ и $$$v$$$ равен $$$c$$$. Обновленный символ может быть равен символу, записанному на этом ребре ранее.

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

Выведите $$$q$$$ строк. В $$$i$$$-й из них выведите «Fou» если дерево не анаграммное после первых $$$i$$$ обновлений.

Иначе выведите «Shi» и $$$\sum{f(c) \cdot ind(c)}$$$ по всем буквам $$$c$$$.

Примеры
Входные данные
3 4
1 ?
1 ?
2 ?
2 a
3 b
2 b
Выходные данные
Shi 351
Shi 1
Fou
Shi 2
Входные данные
5 2
1 ?
1 ?
2 ?
3 ?
4 a
5 b
Выходные данные
Shi 352
Shi 3
Примечание

В первом примере после первого запроса, для каждого символа, вы можете поставить все ребра равными этому символу, и вы получите $$$1$$$ такой символ на каждом пути, так что ответ равен $$$1 \cdot (1+2+\ldots+26) = 351$$$.

В первом примере после второго запроса, вы знаете, что все пути должны быть анаграммой «a», так что все пути должны быть равны «a», так что ответ равен $$$1 \cdot 1 = 1$$$.

В первом примере после третьего запроса, у вас есть два пути со строками «a» и «b», но эти строки не анаграммы, так что ответ «Fou».

В первом примере после четвертого запроса, вы знаете, что все пути должны быть «b», так что ответ равен $$$1 \cdot 2 = 2$$$.

Во втором примере после первого запроса, вы знаете, что $$$f($$$'a'$$$) = 2$$$ и $$$f(c) = 1$$$ для всех остальных символов, так что ответ равен $$$1 \cdot (2 + 3 + \ldots + 26) + 2 = 352$$$.

Во втором примере после второго запроса, вы знаете, что на каждом пути должно быть одно 'a' и одно 'b', так что ответ равен $$$1 \cdot 1 + 1 \cdot 2 = 3$$$.