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

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

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

输入格式

第一行三个整数 $n,m,x_0$。保证 $n,m\ge 1$，$0\le x_0<998244353$ 且 $x_0\ne 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\le a,b<{10}^6$，$0\le c<40$，保证查询操作的出现次数不超过 ${10}^5$。

时间限制：$2\mathtt{\text{s}}$

空间限制：$256\mathtt{\text{MB}}$

下载

样例数据下载