잠긴 상자

잠긴 상자의 비밀번호는 수열 $\{a_n\}$로 정해진다. 수열은 다음과 같이 만든다.

1. 처음에 수열의 길이는 2이고, $a_0 = 0$, $a_1 = 1$이다.

2. 수열에 연산을 여러 번 수행한다. 각 연산은 다음 두 종류 중 하나이다.

   • 종류 W: 수열의 마지막 항에 1을 더한다.
   • 종류 E: 마지막 항이 1이면 마지막에서 두 번째 항에 1을 더한다. 그렇지 않으면 마지막 항에서 1을 빼고, 수열 끝에 항 두 개를 붙인다. 붙인 두 항의 값은 모두 1이다.

상자는 수열 전체를 확인할 수 없으므로, 비밀번호는 함수 $f$로 변환한 뒤의 $\{a_n\}$ 값으로 정한다. 함수 $f$는 다음과 같다.

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

비밀번호는 연산 순서로부터 계산한다. 연산 순서는 갱신으로 바뀔 수 있다. 갱신은 다음 세 종류 중 하나이다.

• APPEND c: 현재 연산 순서의 뒤에 종류 c의 연산을 덧붙인다. c는 W 또는 E이다.
• FLIP l r: 현재 연산 순서에서 $l$번째부터 $r$번째 연산까지(양 끝 포함) 반전한다. 반전은 W를 E로, E를 W로 바꾸는 것이다.
• REVERSE l r: $l$번째부터 $r$번째 연산까지의 순서를 거꾸로 뒤집는다.

첫 줄에 초기 연산 순서의 길이 $n$과 갱신 횟수 $q$가 주어진다. 둘째 줄에는 대문자 E와 W로만 이루어진 길이 $n$의 문자열이 주어지며, 이것이 초기 연산 순서이다. 이어지는 $q$개의 줄에는 위에서 설명한 형식의 갱신이 한 줄에 하나씩 주어진다.

$q+1$개의 줄을 출력한다. 첫 줄에는 초기 연산 순서에 대한 비밀번호를, 이어지는 $q$개의 줄에는 각 갱신 후의 비밀번호를 출력한다. 각 줄에는 정수 두 개를 출력한다. 비밀번호가 $\frac{a}{b}$이고 $a, b > 0$, $\gcd(a,b) = 1$이면, $a$와 $b$를 각각 998244353으로 나눈 나머지를 출력한다. 비밀번호는 항상 양의 유리수이다.

모든 테스트케이스에서 $1 \le n \le 10^5$, $1 \le q \le 10^5$이다.

APPEND 갱신의 $c$는 항상 대문자 W 또는 E이다.

FLIP과 REVERSE 갱신에서는 $1 \le l \le r \le L$이 보장된다. 여기서 $L$은 현재 연산 순서의 길이이다.

APPEND 갱신 때문에 연산 순서의 길이는 최대 $2 \times 10^5$까지 늘어날 수 있다.