Yelekastee is a famous archaeologist from country U. In a recent archaeological expedition, he unearthed an ancient safe. After careful and rigorous research, Yelekastee learned that the password of the safe is related to a sequence $\{a_n\}$. The sequence $\{a_n\}$ can be constructed as follows:

1. Initially, the sequence has a length of 2, with $a_0 = 0, a_1 = 1$.
2. Perform a series of operations on the sequence, where 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, subtract 1 from the last term, and then append two terms to the end of the sequence, both of which are 1.

Due to technical limitations, the safe cannot fully inspect the entire sequence. Therefore, the password of the safe is set to the value of the sequence $\{a_n\}$ after applying the function $f$, where $f$ is defined as:

$$f(a_0, \dots, a_{k-1}, a_k) = \begin{cases} a_0, & k = 0 \\ f\left(a_0, a_1, \dots, a_{k-2}, a_{k-1} + \frac{1}{a_k}\right), & k \geq 1 \end{cases}$$

Yelekastee is not good at calculations, so he has come to you, hoping you can calculate the password of the safe based on the operation sequence he provides. Unfortunately, his memory is not very good, so he will make some modifications to the provided operation sequence at any time. These modifications include the following three types:

• APPEND c: Append an operation of type c to the existing operation sequence, where c is the character W or E.
• FLIP l r: Flip the operations from the $l$-th to the $r$-th in the existing operation sequence (1-indexed, inclusive of endpoints $l$ and $r$, same below), meaning all W become E, and all E become W.
• REVERSE l r: Reverse the operations from the $l$-th to the $r$-th in the existing operation sequence, which means reversing the order of operations in this interval.

Input

The first line contains two positive integers $n, q$, representing 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 represent a modification. The format of each modification is as described in the problem statement.

Output

Output $q + 1$ lines, each containing two integers. The first line represents the password corresponding to the initial operation sequence, and 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$, you need to output the remainders of $a$ and $b$ modulo 998244353 in the corresponding line.

Examples

Input 1

2 3
WE
APPEND E
FLIP 1 2
REVERSE 2 3

Output 1

2 3
3 4
5 3
5 2

Note 1

Constraints

For all test cases: $1 \le n \le 10^5$, $1 \le q \le 10^5$. For APPEND modifications, it is guaranteed that the given c is an uppercase English letter W or E. For FLIP and REVERSE modifications, it is guaranteed that $1 \le l \le r \le L$, where $L$ is the length of the current operation sequence. Note that due to the APPEND operation, the maximum length of the operation sequence can be $2 \times 10^5$.

Special constraint A: It is guaranteed that there will never be two consecutive identical characters in the operation sequence at any time. Special constraint B: It is guaranteed that there are no FLIP modifications. Special constraint C: It is guaranteed that there are no REVERSE modifications.