9433 - 密码箱

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(a0, \ldots , a{k - 1}, a_k) = \begin{cases} a_0, & k = 0 \ f ! \left( a_0, a1, \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 后的余数。

【样例解释 #1】

对于所有测试点：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。

NOI