P7739 [NOI2021] Combination Lock

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.

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

**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$ | ${10}^5$ | B, C | | $11 \sim 14$ | ${10}^5$ | C | | $15 \sim 20$ | ${10}^5$ | 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