The password of a lockbox is determined by a sequence $\{a_n\}$. The sequence $\{a_n\}$ may be constructed as follows:

1. Initially, the length of the sequence is 2 and $a_0=0$, $a_1=1$.
2. Perform some operations on the sequence. Each operation must be 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, then add 1 to the second-to-last term. Otherwise, subtract 1 from the last term of the sequence, and append two terms to the end of the sequence. The values of the two new terms are both 1.

The lockbox cannot check the entire sequence, so the password is set to be the value of $\{a_n\}$ after transformation by function $f$. The function $f$ is defined as follows:

$${\displaystyle f(a_0,\dots ,a_{k-1},a_k)=\{\begin{array}{ll}{a}_0,& k=0\\ f(a_0,a_1,\dots ,a_{k-2},a_{k-1}+\frac{1}{a_k}),& k\ge 1.\end{array}}$$

You need to compute the password based on the sequence of operations. However, the sequence of operations may be updated. The updates are one of the following three types:

• APPEND c: Append an operation of type c after the current sequence of operations (that is used to generate the sequence $\{a_n\}$). c will be either character W or E.

• FLIP l r: Flip the operations between the $l$-th operation and the $r$-th operation in the current sequence of operations (the indices begin with 1, and the update will include the endpoints $l$ and $r$). Here, flipping means switching all W to E and switching all E to W.

• REVERSE l r: Reverse the operations between the $l$-th operation and the $r$-th operation, which means reverse the order of operations in this interval.

Input Specification

The first line of the input contains two integers $n,q$, denoting the length of the initial sequence of operations and the number of updates.

The second line contains a string of length $n$ consisting of upper-case letters E and W, denoting the initial sequence of operations.

For the following $q$ lines, each line specifies an operation. The format is defined in the problem description.

Output Specification

The output consists of $q+1$ lines. Each line contains two integers. The first line denotes the password corresponding to the initial sequence of operations, and the following $q$ lines denote the passwords after each update.

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

Sample Input 1

2 3
WE
APPEND E
FLIP 1 2
REVERSE 2 3

Sample Output 1

2 3
3 4
5 3
5 2

Explanation for Sample Output 1

	Operations	$a_n$	Password
Initial	WE	$(0,1,1,1)$	$\frac{2}{3}$
After 1st update	WEE	$(0,1,2,1)$	$\frac{3}{4}$
After 2nd update	EWE	$(1,1,1,1)$	$\frac{5}{3}$
After 3rd update	EEW	$(2,2)$	$\frac{5}{2}$

Additional Samples

The samples can be found here.

• Sample 2 (code2.in and code2.ans) corresponds to cases 1-4.
• Sample 3 (code3.in and code3.ans) corresponds to cases 5-7.
• Sample 4 (code4.in and code4.ans) corresponds to cases 8-10.
• Sample 5 (code5.in and code5.ans) corresponds to cases 15-20.

Constraints

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

For updates APPEND, it is guaranteed that the given c will be upper-case letter W or E.

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

Please notice because there are updates of type APPEND, the maximum length of the sequence of operations might be as large as $2\times {10}^5$.

Test Case	$n,q\le$	Additional Constraints
1~4	$2000$	None.
5~7	${10}^5$	A
8~10		B, C
11~14		C
15~20		None.

Constraint A: it is guaranteed that at any point there won't be two consecutive identical characters in the sequence of operations.
Constraint B: there are no FLIP updates.
Constraint C: there are no REVERSE updates.