数学考试，一道圆锥曲线的题难住了你，你开始疯狂地笔算。但是，这题实在太难，于是你决定每种思路多尝试尝试。

你的思维过程可以转化为如下过程：

• 有一个随机数产生器，有个内部变量 $x$ 初始时为 $x_0$，每次产生随机数时它会将 $x$ 变为 $(100000005x+20150609) \bmod 998244353$，然后返回 $\lfloor \frac{x}{100} \rfloor$。（$a \bmod b$ 表示 $a$ 除以 $b$ 的余数，该运算的优先级高于加减法。$\lfloor \alpha \rfloor$ 表示 $\alpha$ 向下取整后的结果。）
• 初始时有 $n$ 个点，分别编号为 $1, \dots, n$，按编号从小到大顺序生成第 $i$ 个点的坐标：
  • 把横坐标赋为 $i$。
  • 产生一个随机数 $\hat{y}$，把纵坐标赋为 $\hat{y} \bmod 100001$。
• 有 $m$ 个操作，表示你的思路过程。操作共有三种：
  • C：按顺序产生随机数 $\hat{p}, \hat{y}$，令 $p = \hat{p} \bmod n + 1, y = \hat{y} \bmod 100001$，然后把第 $p$ 个点的纵坐标修改为 $y$。
  • R：按顺序产生随机数 $\hat{p}, \hat{q}$，令 $p = \min\{\hat{p} \bmod n + 1, \hat{q} \bmod n + 1\}, q = \max\{\hat{p} \bmod n + 1, \hat{q} \bmod n + 1\}$，把编号大于等于 $p$ 小于等于 $q$ 的点的纵坐标 $y$ 改为 $100000 - y$。
  • Q $a$ $b$ $c$：查询操作。按顺序产生随机数 $\hat{p}, \hat{q}$，令 $p = \min\{\hat{p} \bmod n + 1, \hat{q} \bmod n + 1\}, q = \max\{\hat{p} \bmod n + 1, \hat{q} \bmod n + 1\}$，求最小的整数 $t$ 使得：对于所有编号大于等于 $p$ 小于等于 $q$ 的点 $(x, y)$ 都满足 $ax + by + cxy \leq t$。（$a, b, c$ 均为非负整数）

输入格式

第一行三个整数 $n, m, x_0$。保证 $n, m \geq 1$，$0 \leq x_0 < 998244353$ 且 $x_0 \neq 340787122$。

接下来 $m$ 行，每行表示一个操作，格式如前所述。

输出格式

对于每个查询操作输出一个整数表示最小的 $t$。

样例一

input

3 3 2705443
C
R
Q 872784 195599 7

output

13035048532

explanation

最开始三个点的坐标分别是 $(1,91263),(2,33372),(3,10601)$。

第一个操作把第三个点的坐标改成了 $(3,94317)$。

第二个操作修改了区间 $[2,3]$，第二个点变成了 $(2,66628)$，第三个点变成了 $(3,5683)$。

最后一个操作询问区间 $[2,3]$，可以发现最小的 $t$ 是 $13035048532$。

样例二

见样例数据下载。

限制与约定

所有数据中，对于所有查询操作保证 $0 \leq a, b < 10^6$，$0 \leq c < 40$，保证查询操作的出现次数不超过 $10^5$。

时间限制：$2\texttt{s}$

空间限制：$256\texttt{MB}$

下载

样例数据下载