CF1168D.Anagram Paths

Toad Ilya has a rooted binary tree with vertex $1$ being the root. A tree is a connected graph without cycles. A tree is rooted if one vertex is selected and called the root. A vertex $u$ is a child of a vertex $v$ if $u$ and $v$ are connected by an edge and $v$ is closer to the root than $u$. A leaf is a non-root vertex that has no children.

In the tree Ilya has each vertex has at most two children, and each edge has some character written on it. The character can be a lowercase English letter or the question mark '?'.

Ilya will $q$ times update the tree a bit. Each update will replace exactly one character on some edge. After each update Ilya needs to find if the tree is anagrammable and if yes, find its anagramnity for each letter. Well, that's difficult to explain, but we'll try.

To start with, a string $a$ is an anagram of a string $b$ if it is possible to rearrange letters in $a$ (without changing the letters itself) so that it becomes $b$. For example, the string "fortyfive" is an anagram of the string "overfifty", but the string "aabb" is not an anagram of the string "bbba".

Consider a path from the root of the tree to a leaf. The characters on the edges on this path form a string, we say that this string is associated with this leaf. The tree is anagrammable if and only if it is possible to replace each question mark with a lowercase English letter so that for all pair of leaves the associated strings for these leaves are anagrams of each other.

If the tree is anagrammable, then its anagramnity for the letter $c$ is the maximum possible number of letters $c$ in a string associated with some leaf in a valid replacement of all question marks.

Please after each update find if the tree is anagrammable and if yes, find the $\sum{f(c) \cdot ind(c)}$ for all letters $c$, where $f(c)$ is the anagramnity for the letter $c$, and $ind(x)$ is the index of this letter in the alphabet ($ind($"a"$) = 1$, $ind($"b"$) = 2$, ..., $ind($"z"$) = 26$).

蟾蜍伊利亚有一棵以顶点 $1$ 为根的有根二叉树。树是无环的连通图；若树中指定一个顶点作为根，则称其为有根树。若顶点 $u$ 与 $v$ 由一条边相连，且 $v$ 比 $u$ 更靠近根，则称 $u$ 是 $v$ 的一个子节点。叶子节点是指非根节点且没有子节点的顶点。

在伊利亚所拥有的这棵树中，每个顶点至多有两个子节点，且每条边上都标有一个字符。该字符可以是小写英文字母或问号 '?'。

伊利亚将进行 $q$ 次对树的更新操作。每次更新操作恰好修改某条边上一个字符。每次更新后，伊利亚都需要判断该树是否“可变位构词”（anagrammable）；若可，则还需对每个字母求出其“变位构词性”（anagramnity）。这概念较难解释，但我们将尽力说明。

首先，若字符串 $a$ 可通过重排其字母（不改变字母本身）得到字符串 $b$，则称 $a$ 是 $b$ 的一个变位词（anagram）。例如，字符串 "fortyfive" 是 "overfifty" 的一个变位词，但 "aabb" 不是 "bbba" 的变位词。

考虑从树根到某一叶子节点的一条路径。该路径上各边所标记的字符按顺序构成一个字符串，我们称该字符串关联于该叶子节点。当且仅当能够将所有问号 '?' 替换为小写英文字母，使得任意两个叶子节点所关联的字符串互为变位词时，该树被称为可变位构词的（anagrammable）。

若该树可变位构词，则其关于字母 $c$ 的变位构词性（anagramnity） 定义为：在所有合法的问号替换方案下，某个叶子节点所关联字符串中字母 $c$ 出现次数的最大可能值。

请在每次更新后，判断该树是否可变位构词；若可，则计算 $\sum{f(c) \cdot ind(c)}$（对所有字母 $c$ 求和），其中 $f(c)$ 表示字母 $c$ 的变位构词性，而 $ind(x)$ 表示字母 $x$ 在字母表中的序号（即 $ind($"a"$) = 1$，$ind($"b"$) = 2$，……，$ind($"z"$) = 26$）。

The first line of input contains two integers $n$ and $q$ ($2 \leq n \leq 150\,000$, $1 \leq q \leq 150\,000$) — the number of vertices in the tree and the number of queries.

The next $n-1$ lines describe the initial tree. The $i$-th of them contains an integer $p_i$ and a character $c_i$ ($1 \leq p_i \leq i$, $c_i$ is a lowercase English letter or the question mark '?') describing an edge between vertices $p_i$ and $i+1$ with character $c_i$ written on it.

The root of this tree is the vertex $1$, and each vertex has at most two children.

The next $q$ lines describe the queries. The $i$-th of them contains two integers $v$ and $c$ ($2 \leq v \leq n$, $c$ is a lowercase English letter or the question mark '?'), meaning that updated character on the edge between $p_{v-1}$ to $v$ is $c$. The updated character can be the same as was written before.

输入的第一行包含两个整数 $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$。更新后的字符可能与原先的字符相同。

Output $q$ lines. In the $i$-th of them print "Fou" if the tree is not anagrammable after the first $i$ updates.

Otherwise output "Shi" and the $\sum{f(c) \cdot ind(c)}$ for all letters $c$.

输出 $q$ 行。在第 $i$ 行中，如果经过前 $i$ 次更新后该树不再具有回文构型（anagrammable），则输出 “Fou”。

否则，输出 “Shi” 以及对所有字母 $c$ 的 $\sum{f(c) \cdot ind(c)}$ 值。

In the first example after the first query, for each character, you can set all edges equal to that character, and you will get $1$ such character on each path, so the answer is $1 \cdot (1+2+\ldots+26) = 351$.

In the first example after the second query, you know that all paths should be an anagram of "a", so all paths should be "a", so the answer is $1 \cdot 1 = 1$.

In the first example after the third query, you have two paths with strings "a" and "b", but these strings are not anagrams, so the answer is "Fou".

In the first example after the fourth query, you know that all paths should be "b", so the answer is $1 \cdot 2 = 2$.

In the second example after the first query, you know that $f($'a'$) = 2$ and $f(c) = 1$ for all other characters, so the answer is $1 \cdot (2 + 3 + \ldots + 26) + 2 = 352$.

In the second example after the second query, you know that each path should contain one 'a' and one 'b', so the answer is $1 \cdot 1 + 1 \cdot 2 = 3$.

在第一个样例中，第一次查询之后，对于每个字符，你可以将所有边都设为该字符，这样每条路径上恰好出现 $1$ 个该字符，因此答案为 $1 \cdot (1+2+\ldots+26) = 351$。

在第一个样例中，第二次查询之后，已知所有路径都应是字符串 "a" 的一个变位词（anagram），即所有路径都必须是 "a"，因此答案为 $1 \cdot 1 = 1$。

在第一个样例中，第三次查询之后，你得到两条路径，对应的字符串分别为 "a" 和 "b"，但这两个字符串互不为变位词，因此答案为 "Fou"。

在第一个样例中，第四次查询之后，已知所有路径都必须是 "b"，因此答案为 $1 \cdot 2 = 2$。

在第二个样例中，第一次查询之后，已知 $f($'a'$) = 2$，且对所有其他字符 $c$ 有 $f(c) = 1$，因此答案为 $1 \cdot (2 + 3 + \ldots + 26) + 2 = 352$。

在第二个样例中，第二次查询之后，已知每条路径都应恰好包含一个 'a' 和一个 'b'，因此答案为 $1 \cdot 1 + 1 \cdot 2 = 3$。