D-★★飞马祝福语★★_兰州大学第一届『飞马杯』程序设计竞赛（同步赛）

时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

在兰州大学第一届“飞马杯”程序设计竞赛中，我们收到了很多来自同学们的祝福信。我们认为祝福信的任意子序列都是一条祝福语，子序列为原字符串中删去若干字符，剩余字符相对位置不变形成的序列。例如ac，abcd均是abcd的子序列，而ca则不是abcd的子序列。

如果一条祝福语与FeiMa完全相同(包括大小写)，我们称这条祝福语为“飞马祝福语”。例如，FeiMa是“飞马祝福语”，而Feima，FeiMaa则不是。

然而，令我们非常震惊的是，出现不明身份人员混入命题组，私自重启已关闭的服务器，并且在服务器上多次修改祝福信，被发现后及时制止。为了挽回损失并且更好地感受来自同学们的祝福，现在需要统计祝福信在每次修改之后依然包含多少条“飞马祝福语”。由于数量可能很大，请对 $998244353$ 取模后作为答案输出。

输入描述:

第一行一个整数 $T \; (1 \leq T \leq 10^{5})$ ，表示测试用例的数量。

对于每组测试用例，第一行两个整数 $n,q \; (1 \leq n,q \leq 10^{5})$ ，分别表示祝福信的长度和修改次数；

接下来一行，一个长度为 $n$ 的字符串 $s$ ，表示收到的祝福信；

接下来 $q$ 行，第 $i \; (1 \leq i \leq q)$ 行两个整数 $l_{i},r_{i} \; (1 \leq l_{i} \leq r_{i} \leq n)$ 和一个英文字母 $x_{i}$ ，表示不明身份人员将字符串 $s$ 的区间 $[l_{i},r_{i}]$ 中所有字符修改为 $x_{i}$ 。

对于全部测试用例，保证祝福信中仅包含大小写英文字母，且 $\sum n, \sum q \leq 10^{5}$ 。

输出描述:

对于每组测试用例的每次修改，输出一行一个整数表示答案。

示例1

输入

复制

1
15 2
FeimaFeiMaFeima
4 6 M
7 10 a

输出

复制

12
15

说明

在第一次修改之后，祝福信变为 FeiMMMeiMaFeima，其中包含 $12$ 条飞马祝福语。

在第二次修改之后，祝福信变为 FeiMMMaaaaFeima，其中包含 $15$ 条飞马祝福语。