Rikka 按如下方式生成整数序列 $u_1, u_2, \dots$：她首先生成 $x_1, x_2, \dots$，其中 $x_i = (100\,000\,005 \cdot x_{i-1} + 20\,150\,609) \pmod{998\,244\,353}$，然后令 $u_i = \lfloor \frac{x_i}{100} \rfloor$。

初始时，笛卡尔坐标系上有 $n$ 个点。第 $i$ 个点的坐标为 $(i, u_i \pmod{100\,001})$。 此后，依次进行 $m$ 次操作。第 $i$ 次操作属于以下三种类型之一：“C”、“R” 或 “Q”。 令 $p_i = \min\{u_{n+2i-1} \pmod n, u_{n+2i} \pmod n\} + 1$ 且 $q_i = \max\{u_{n+2i-1} \pmod n, u_{n+2i} \pmod n\} + 1$。

• 如果第 $i$ 次操作类型为 “C”，将第 $(u_{n+2i-1} \pmod n + 1)$ 个点变换为 $(u_{n+2i-1} \pmod n + 1, u_{n+2i} \pmod{100\,001})$。
• 如果第 $i$ 次操作类型为 “R”，对于所有满足 $p_i \le x \le q_i$ 的 $x$，将点 $(x, y)$ 变换为 $(x, 100\,000 - y)$。
• 如果第 $i$ 次操作类型为 “Q”，考虑当前所有满足 $p_i \le x \le q_i$ 的点 $(x, y)$，给定 $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 < 998\,244\,353, x_0 \neq 340\,787\,122$)。 接下来的 $m$ 行，第 $i$ 行以一个字符 $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

3 3 2705443
C
R
Q 872784 195599 7

输出 1

13035048532

说明

初始时，三个点分别位于 $(1, 91263), (2, 33372)$ 和 $(3, 10601)$。 第一次操作将第三个点变为 $(3, 94317)$。