Problem Description

Yelekastee is a famous archaeologist in Country U. In a recent excavation, he unearthed an ancient combination lock. After careful and rigorous research, Yelekastee learned that the lock’s password is related to a certain sequence $\{ a_n \}$. The sequence $\{ a_n \}$ can be constructed as follows:

1. Initially, the sequence has length $2$ and $a_0 = 0, a_1 = 1$.
2. Perform a number of operations on the sequence in order. Each operation is one of the following two types:

• Type W: add $1$ to the last term of the sequence.
• Type E: if the last term of the sequence is $1$, add $1$ to the second-to-last term; otherwise, first subtract $1$ from the last term, then append two more terms to the end of the sequence, both equal to $1$.

Due to technical limitations, the lock cannot fully inspect the entire sequence. Therefore, the lock’s password is defined as the value obtained by applying a function $f$ to the sequence $\{ a_n \}$, where $f$ is defined as:

$$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 is not good at calculations, so he came to you and hopes you can compute the lock’s password from the operation sequence he provides. Unfortunately, his memory is not very good, so he will modify the operation sequence from time to time. These modifications include the following three types:

• APPEND c: append one operation of type c to the end of the current operation sequence, where c is the character W or E.
• FLIP l r: flip the $l$-th to the $r$-th operations (indices start from $1$, and the modification includes both endpoints $l$ and $r$, same below), i.e., change every W to E and every E to W.
• REVERSE l r: reverse the order of the $l$-th to the $r$-th operations, i.e., reverse this segment of operations.

Input Format

The first line contains two positive integers $n, q$, denoting the initial length of the operation sequence and the number of modifications, respectively.

The second line contains a string of length $n$ consisting only of uppercase letters W and E, representing the initial operation sequence.

The next $q$ lines each describe one modification. The format of each modification is as described in the Description.

Output Format

Output a total of $q + 1$ lines, each containing two integers. The first line is the password corresponding to the initial operation sequence. The next $q$ lines output the password corresponding to the operation sequence after each modification.

It is easy to see that the password must be a positive rational number. If the true password is $\frac{a}{b}$, where $a, b > 0$ and $\gcd(a, b) = 1$, then on the corresponding line you should output $a$ and $b$ modulo $998244353$, in this order.

2 3
WE
APPEND E
FLIP 1 2
REVERSE 2 3

2 3
3 4
5 3
5 2

Hint

Sample Explanation #1

	Operation sequence	Sequence $\{ a_n \}$	Password
Initial	WE	$(0, 1, 1, 1)$	$\frac{2}{3}$
After the 1st modification	WEE	$(0, 1, 2, 1)$	$\frac{3}{4}$
After the 2nd modification	EWE	$(1, 1, 1, 1)$	$\frac{5}{3}$
After the 3rd modification	EEW	$(2, 2)$	$\frac{5}{2}$

Sample #2

See the attachments code/code2.in and code/code2.ans.

This sample satisfies the same constraint conditions as testdata $1 \sim 4$.

Sample #3

See the attachments code/code3.in and code/code3.ans.

This sample satisfies the same constraint conditions as testdata $5 \sim 7$.

Sample #4

See the attachments code/code4.in and code/code4.ans.

This sample satisfies the same constraint conditions as testdata $8 \sim 10$.

Sample #5

See the attachments code/code5.in and code/code5.ans.

This sample satisfies the same constraint conditions as testdata $15 \sim 20$.

Constraints

For all test points: $1 \le n \le {10}^5$, $1 \le q \le {10}^5$.

For APPEND modifications, it is guaranteed that c is an uppercase letter W or E.

For FLIP and REVERSE modifications, it is guaranteed that $1 \le l \le r \le L$, where $L$ is the current length of the operation sequence.

Note that due to the APPEND operation, the maximum possible length of the operation sequence is $2 \times {10}^5$.

Test point ID	$n, q \le$	Special constraints
$1 \sim 4$	$2000$	None
$5 \sim 7$	${10}^5$	A
$8 \sim 10$		B, C
$11 \sim 14$		C
$15 \sim 20$		None

Special constraint A: it is guaranteed that at any time, there will not be two identical consecutive characters in the operation sequence.

Special constraint B: it is guaranteed that there are no FLIP modifications.

Special constraint C: it is guaranteed that there are no REVERSE modifications.

Translated by ChatGPT 5