异位路径

• 时间限制：5 秒
• 内存限制：256 MiB

题目描述

给定一棵以顶点 $1$ 为根的二叉树。每个顶点最多有两个子节点，每条边上写有一个小写英文字母或问号 ?。

一条从根到叶子的路径上的边字符依次组成一个字符串。你可以把每个问号替换成任意小写英文字母；如果能使所有叶子对应的字符串两两互为字母异位词，就称这棵树能变为一棵异位树。

若树能变为异位树，对每个字母 $c$ 定义 $f(c)$：在所有合法的问号替换方案中，叶子路径字符串内字母 $c$ 出现次数的最大值。

现在进行 $q$ 次更新，每次修改一条边上的字符。每次更新后：

• 若树不能变为异位树，输出 Fou；
• 否则输出 Shi 以及$$\sum_{c=\mathtt a}^{\mathtt z} f(c)\cdot \operatorname{ind}(c),$$其中 $\operatorname{ind}(\mathtt a)=1,\operatorname{ind}(\mathtt b)=2,\ldots,\operatorname{ind}(\mathtt z)=26$。

输入格式

第一行包含两个整数 $n,q$，分别表示顶点数和更新次数。

接下来 $n-1$ 行描述初始树。第 $i$ 行包含一个整数 $p_i$ 和一个字符 $c_i$，表示顶点 $p_i$ 与顶点 $i+1$ 之间的边上写有 $c_i$。保证 $1\le p_i\le i$，且每个顶点最多有两个子节点。

接下来 $q$ 行，每行包含一个整数 $v$ 和一个字符 $c$，表示把顶点 $p_{v-1}$ 与顶点 $v$ 之间的边字符改为 $c$。更新后的字符可以与原字符相同。

字符 $c_i,c$ 均为小写英文字母或问号 ?。

输出格式

输出 $q$ 行。按题目描述，对每次更新输出 Fou，或输出 Shi 和所求整数。

样例输入 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

数据范围

对于所有数据，$2\le n\le150000$，$1\le q\le150000$，$1\le p_i\le i$，$2\le v\le n$。

提示

在样例一的第一次更新后，每个字母都能单独作为所有路径中的字符，因此答案为 $1+2+\cdots+26=351$。第二次更新后只能取字母 a，第三次更新后两条路径的固定字符冲突，第四次更新后只能取字母 b。