시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 256 MB 0 0 0 0.000%

문제

Rikka generates an integer sequence $u_1, u_2, \ldots$ as follows: she generates $x_1, x_2, \ldots$, where $x_i = (100\,000\,005 \cdot x_{i - 1} + 20\,150\,609) \bmod 998\,244\,353$, and then sets $u_i = \lfloor \frac{x_i}{100} \rfloor$.

Initially, there are $n$ points on the Cartesian plane. The $i$-th point has coordinates $(i, u_{i} \bmod 100\,001)$. After that, $m$ operations are performed subsequently. The $i$-th operation has one of the three types: "C", "R", and "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 of type "C", transform the $(u_{n + 2i - 1} \bmod n + 1)$-th point into $(u_{n + 2i - 1} \bmod n + 1, u_{n + 2i} \bmod 100\,001)$.
• If the $i$-th operation is of type "R", for all $x$ such that $p_i \leq x \leq q_i$, transform the point $(x, y)$ into $(x, 100\,000 - y)$.
• If the $i$-th operation is of type "Q", consider all currently existing points $(x, y)$ such that $p_i \leq x \leq q_i$ and, given $a_i$, $b_i$ and $c_i$, find $\max\{ a_{i} \cdot x + b_{i} \cdot y + c_{i} \cdot x \cdot y \}$.

입력

The first line contains three integers: $n$, $m$, and $x_0$ ($1 \leq n \leq 10^5$, $1 \leq m \leq 10^6$, $0 \leq x_0 < 998\,244\,353$, $x_0 \neq 340\,787\,122$).

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

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

출력

For each operation of type "Q", output an integer which denotes the maximum.

예제 입력 1

3 3 2705443
C
R
Q 872784 195599 7


예제 출력 1

13035048532


힌트

Initially, the three points lie in $(1, 91263)$, $(2, 33372)$ and $(3, 10601)$ respectively.

The first operation changes the third point to $(3, 94317)$.