Conic Section

Rikka generates an integer sequence $u_1, u_2, \ldots$ as follows. She first generates $x_1, x_2, \ldots$ with $x_i = (100000005 \cdot x_{i-1} + 20150609) \bmod 998244353$, then sets $u_i = \lfloor x_i / 100 \rfloor$.

Initially, there are $n$ points on the Cartesian plane. The $i$-th point has coordinates $(i, u_i \bmod 100001)$. Then $m$ operations are performed in order. The $i$-th operation is one of three types: C, R, or Q.

Let $p_i = \min\{u_{n+2i-1} \bmod n, u_{n+2i} \bmod n\} + 1$ and $q_i = \max\{u_{n+2i-1} \bmod n, u_{n+2i} \bmod n\} + 1$.

• If the $i$-th operation is C, replace the $(u_{n+2i-1} \bmod n + 1)$-th point with $(u_{n+2i-1} \bmod n + 1, u_{n+2i} \bmod 100001)$.
• If the $i$-th operation is R, replace every point $(x, y)$ with $p_i \le x \le q_i$ by $(x, 100000 - y)$.
• If the $i$-th operation is Q, consider all currently existing points $(x, y)$ with $p_i \le x \le q_i$. Given $a_i$, $b_i$, and $c_i$, find $\max\{a_i \cdot x + b_i \cdot y + c_i \cdot x \cdot y\}$ over these points.

The first line contains three integers $n$, $m$, and $x_0$ ($1 \le n \le 10^5$, $1 \le m \le 10^6$, $0 \le x_0 < 998244353$, $x_0 \neq 340787122$).

Each of the following $m$ lines starts with a character $t_i$, the type of the operation, which is C, R, or Q. If $t_i$ is Q, three integers $a_i$, $b_i$, $c_i$ follow ($0 \le a_i, b_i < 10^6$, $0 \le c_i < 40$).

It is guaranteed that the number of Q operations does not exceed $10^5$.

For each Q operation, output the maximum value on one line.

Initially, the three points are at $(1, 91263)$, $(2, 33372)$, and $(3, 10601)$. The first operation changes the third point to $(3, 94317)$.