[NOI2021] 密码箱

Yelekastee 是 U 国著名的考古学家。在最近的一次考古行动中，他发掘出了一个远古时期的密码箱。经过周密而严谨的考证，Yelekastee 得知密码箱的密码和某一个数列 $\{ a_n \}$ 相关。数列 $\{ a_n \}$ 可以用如下方式构造出来： 1. 初始时数列长度为 $2$ 且有 $a_0 = 0, a_1 = 1$； 2. 对数列依次进行若干次操作，其中每次操作是以下两种类型之一： - `W` 类型：给数列的**最后一项**加 $1$。 - `E` 类型：若数列的**最后一项**为 $1$，则给倒数第二项加 $1$；否则先给数列的**最后一项**减 $1$，接着在数列尾再加两项，两项的值都是 $1$。 受到技术限制，密码箱并没有办法完整检查整个数列，因此密码箱的密码设定为数列 $\{ a_n \}$ 经过函数 $f$ 作用后的值，其中 $f$ 的定义如下： $$ f(a_0, \ldots , a_{k - 1}, a_k) = \begin{cases} a_0, & k = 0 \\ f \! \left( a_0, a_1, \ldots , a_{k - 2}, a_{k - 1} + \frac{1}{a_k} \right) \! , & k \ge 1 \end{cases} $$ Yelekastee 并不擅长运算，因此他找到了你，希望你能根据他提供的操作序列计算出密码箱的密码。不幸的是，他的记性并不是很好，因此他会随时对提供的操作序列做出一些修改，这些修改包括以下三种： - `APPEND c`，在现有操作序列后追加一次 `c` 类型操作，其中 `c` 为字符 `W` 或 `E`。 - `FLIP l r`，反转现有操作序列中第 $l$ 个至第 $r$ 个（下标从 $1$ 开始，修改包含端点 $l$ 和 $r$，下同）操作，即所有 `W` 变为 `E`，所有 `E` 变为 `W`。 - `REVERSE l r`，翻转现有操作序列中第 $l$ 个至第 $r$ 个操作，也就是将这个区间中的操作逆序。

输入第一行包含两个正整数 $n, q$，分别表示初始的操作序列长度和修改的次数。 第二行包含一个长为 $n$ 且仅包含大写字母 `W` 和 `E` 的字符串，表示初始操作序列。 接下来 $q$ 行，每行表示一次修改。每种修改的格式如【题目描述】所述。

输出共 $q + 1$ 行，每行两个整数，其中第一行表示初始操作序列对应的密码，接下来 $q$ 行则分别输出每次修改之后的操作序列对应的密码。 容易发现密码一定是正有理数。若真实的密码为 $\frac{a}{b}$，其中 $a, b > 0$ 且 $\gcd(a, b) = 1$，则你需要在对应的行内顺次输出 $a$ 和 $b$ 模 $998244353$ 后的余数。

2 3
WE
APPEND E
FLIP 1 2
REVERSE 2 3

2 3
3 4
5 3
5 2

**【样例解释 #1】** | | 操作序列 | 数列 $\{ a_n \}$ | 密码 | |:-:|:-:|:-:|:-:| | 初始 | `WE` | $(0, 1, 1, 1)$ | $\frac{2}{3}$ | | 第一次修改后 | `WEE` | $(0, 1, 2, 1)$ | $\frac{3}{4}$ | | 第二次修改后 | `EWE` | $(1, 1, 1, 1)$ | $\frac{5}{3}$ | | 第三次修改后 | `EEW` | $(2, 2)$ | $\frac{5}{2}$ | **【样例 #2】** 见附件 `code/code2.in` 与 `code/code2.ans`。 该样例与测试数据 $1 \sim 4$ 满足同样的约束条件。 **【样例 #3】** 见附件 `code/code3.in` 与 `code/code3.ans`。 该样例与测试数据 $5 \sim 7$ 满足同样的约束条件。 **【样例 #4】** 见附件 `code/code4.in` 与 `code/code4.ans`。 该样例与测试数据 $8 \sim 10$ 满足同样的约束条件。 **【样例 #5】** 见附件 `code/code5.in` 与 `code/code5.ans`。 该样例与测试数据 $15 \sim 20$ 满足同样的约束条件。 **【数据范围】** 对于所有测试点：$1 \le n \le {10}^5$，$1 \le q \le {10}^5$。 对于 `APPEND` 修改，保证给出的 `c` 为大写英文字母 `W` 或 `E`。 对于 `FLIP` 和 `REVERSE` 修改，保证 $1 \le l \le r \le L$，其中 $L$ 是当前操作序列的长度。 请注意由于有 `APPEND` 操作，操作序列的长度最大可能有 $2 \times {10}^5$。 | 测试点编号 | $n, q \le$ | 特殊限制 | |:-:|:-:|:-:| | $1 \sim 4$ | $2000$ | 无 | | $5 \sim 7$ | ${10}^5$ | A | | $8 \sim 10$ | ${10}^5$ | B，C | | $11 \sim 14$ | ${10}^5$ | C | | $15 \sim 20$ | ${10}^5$ | 无 | 特殊限制 A：保证在任意时刻操作序列中不会出现连续相同的两个字符。 特殊限制 B：保证没有 `FLIP` 修改。 特殊限制 C：保证没有 `REVERSE` 修改。