题目描述

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,\cdots,a_{k−1},a_k)= \begin{cases} a_0,&k=0\\ f(a_0,\cdots,a_{k−1}+\frac{1}{a_k}),&k\geq 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$ 个操作，也就是将这个区间中的操作逆序。

输入格式

从文件 code.in 中读入数据。

输入第一行包含两个正整数 $n,q$，分别表示初始的操作序列长度和修改的次数。

第二行包含一个长为 $n$ 且仅包含大写字母 W 和 E 的字符串，表示初始操作序列。

接下来 $q$ 行，每行表示一次修改。每种修改的格式如「题目描述」所述。

输出格式

输出到文件 code.out 中。

输出共 $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\}$	密码
初始	$\text{WE}$	$(0,1,1,1)$	$\frac{2}{3}$
第一次修改后	$\text{WEE}$	$(0,1,2,1)$	$\frac{3}{4}$
第二次修改后	$\text{EWE}$	$(1,1,1,1)$	$\frac{5}{3}$
第三次修改后	$\text{EEW}$	$(2,2)$	$\frac{5}{2}$

样例 2

见选手目录下的 code2.in 与 code2.ans。

该样例与测试数据 $1\sim 4$ 满足同样的约束条件。

样例 3

见选手目录下的 code3.in 与 code3.ans。

该样例与测试数据 $5\sim 7$ 满足同样的约束条件。

样例 4

见选手目录下的 code4.in 与 code4.ans。

该样例与测试数据 $8\sim 10$ 满足同样的约束条件。

样例 5

见选手目录下的 code5.in 与 code5.ans。

该样例与测试数据 $15\sim 20$ 满足同样的约束条件。

测试点约束

对于所有测试点：$1 \leq n \leq 10^5$，$0 \leq q \leq 10^5$。

对于 APPEND 修改，保证给出的 c 为大写英文字母 W 或 E。

对于 FLIP 和 REVERSE 修改，保证 $1 \leq l \leq r \leq L$，其中 $L$ 是当前操作序列的长度。

请注意由于有 APPEND 操作，操作序列的长度最大可能有 $2\times 10^5$。

测试点编号	$n,q\leq$	特殊限制
$1\sim 4$	$2000$	无
$5\sim 7$	$10^5$	$A$
$8\sim 10$		$B,C$
$11\sim 14$		$C$
$15\sim 20$		无

特殊限制 $A$：保证在任意时刻操作序列中不会出现连续相同的两个字符。

特殊限制 $B$：保证没有 FLIP 修改。

特殊限制 $C$：保证没有 REVERSE 修改。