Toad Ilya 有一个有根二叉树,顶点 $$$1$$$ 为根。树是没有环的连通图。如果选择一个顶点并称为根,则一棵树就有根。如果 $$$u$$$ 和 $$$v$$$ 通过边连接,并且 $$$v$$$ 比 $$$u$$$ 更靠近根,则顶点 $$$u$$$ 是顶点 $$$v$$$ 的子节点。叶子是没有子节点的非根顶点。
在 Ilya 树中,每个顶点最多有两个子节点,并且每条边上都写有一些字符。该字符可以是小写英文字母或问号“?”。
Ilya 将 $$$q$$$ 次稍微更新一下树。每次更新将恰好替换某些边缘上的一个字符。每次更新后,Ilya 需要查找该树是否可进行字谜重组,如果是,则查找每个字母的字谜重组。嗯,这很难解释,但我们会尝试。
首先,如果可以重新排列 $$$a$$$ 中的字母(不更改字母本身),使其变为 $$$b$$$,则字符串 $$$a$$$ 是字符串 $$$b$$$ 的字谜词。例如,字符串“forty Five”是字符串“overfifty”的字谜词,但字符串“aabb”不是字符串“bbba”的字谜词。
考虑从树根到叶子的路径。这条路径上边缘上的字符形成一个字符串,我们说这个字符串与这个叶子相关联。当且仅当可以用小写英文字母替换每个问号时,该树才是可重组的,这样对于所有叶子对,这些叶子的关联字符串都是彼此的重组词。
如果树是可字谜的,则字母 $$$c$$$ 的字谜是与所有问号的有效替换中的某个叶子关联的字符串中字母 $$$c$$$ 的最大可能数量。
请在每次更新后查找该树是否可字谜,如果是,请查找所有字母 $$$c$$$ 的 $$$\sum{f(c) \cdot ind(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$$$ 更新后不可重新语法,则在第 $$$i$$$ 中打印“Fou”。
否则输出“Shi”和所有字母 $$$c$$$ 的 $$$\sum{f(c) \cdot ind(c)}$$$。
示例
输入 #1
3 4 1 ? 1 ? 2 ? 2 a 3 b 2 b
输出 #1
Shi 351 Shi 1 Fou Shi 2
输入 #2
5 2 1 ? 1 ? 2 ? 3 ? 4 a 5 b
输出 #2
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$$$。