25069번 - The Locked Box 다국어

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{cases} a_0, & k = 0 \\ f\left(a_0,a_1,\dots,a_{k-2},a_{k-1}+\frac{1}{a_k}\right), & k \ge 1. \end{cases}$$

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.

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.

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 $998\,244\,353$ in the corresponding line.

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$.