19315번 - Conic Section 다국어

문제

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.

제한

힌트

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

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