원뿔 곡선

Rikka는 다음과 같이 정수 수열 $u_1, u_2, \ldots$을 만든다. 먼저 $x_i = (100000005 \cdot x_{i-1} + 20150609) \bmod 998244353$으로 $x_1, x_2, \ldots$을 구하고, 그다음 $u_i = \lfloor x_i / 100 \rfloor$로 둔다.

처음에 좌표평면 위에 $n$개의 점이 있다. $i$번째 점의 좌표는 $(i, u_i \bmod 100001)$이다. 이후 $m$개의 연산을 순서대로 수행한다. $i$번째 연산은 C, R, Q 중 하나의 종류를 가진다.

$p_i = \min\{u_{n+2i-1} \bmod n, u_{n+2i} \bmod n\} + 1$, $q_i = \max\{u_{n+2i-1} \bmod n, u_{n+2i} \bmod n\} + 1$로 정의한다.

• $i$번째 연산이 C이면, $(u_{n+2i-1} \bmod n + 1)$번째 점을 $(u_{n+2i-1} \bmod n + 1, u_{n+2i} \bmod 100001)$로 바꾼다.
• $i$번째 연산이 R이면, $p_i \le x \le q_i$를 만족하는 모든 점 $(x, y)$를 $(x, 100000 - y)$로 바꾼다.
• $i$번째 연산이 Q이면, 현재 존재하는 점 중 $p_i \le x \le q_i$를 만족하는 점들을 대상으로 한다. 주어진 $a_i$, $b_i$, $c_i$에 대해 이 점들의 $\max\{a_i \cdot x + b_i \cdot y + c_i \cdot x \cdot y\}$를 구한다.

첫 줄에 정수 $n$, $m$, $x_0$이 주어진다($1 \le n \le 10^5$, $1 \le m \le 10^6$, $0 \le x_0 < 998244353$, $x_0 \neq 340787122$).

이어지는 $m$개의 줄은 연산의 종류를 나타내는 문자 $t_i$로 시작하며, C, R, Q 중 하나이다. $t_i$가 Q이면 정수 $a_i$, $b_i$, $c_i$가 뒤따른다($0 \le a_i, b_i < 10^6$, $0 \le c_i < 40$).

Q 연산의 개수는 $10^5$을 넘지 않는다고 보장된다.

Q 연산마다 최댓값을 한 줄에 출력한다.

처음에 세 점은 $(1, 91263)$, $(2, 33372)$, $(3, 10601)$에 있다. 첫 번째 연산은 세 번째 점을 $(3, 94317)$로 바꾼다.