U172682 冷门trick: 单调区间线性求和

（与题意无关） 这玩意是啥？ 这是一个听人随口提到的冷门技巧，可以在线性时间内求出“单调区间”的“和”。它只能查询，对查询还有要求，并且不支持修改 什么是“单调区间”？不是指区间里的数单调，是指区间的左端点/右端点 **都** 单调递增 什么是 “和”？只要可以合并，有结合律，都可以，甚至可以没有交换律。当然，肯定也不单单是simple的加起来。 为什么要有这样的东西？ 前缀和固然很快，但它要信息可减；线段树固然适用范围广，但它多一个log。 而这个东西，不但快，在特定条件下，也能解决很多东西。 关于讲解：在 [这里](https://www.cnblogs.com/LightningUZ/p/15115111.html)

现在你要做一个很简单的问题：给你一个序列 $a$，长度为 $n$。你要支持 $q$ 个询问，每次询问给出 $l_i,r_i$，求 $\prod\limits_{j=l_i}^{r_i} a_j$，对 59861874 取模。 #### 保证 $l_i,r_i$ **分别递增**。

首先输入 $n,q$，然后给定一个 $seed$。接下来用如下代码生成 $a_i,l_i,r_i$： ```cpp int uu=1; int rnd() {uu=uu*seed%100003; return (uu

假设第 $i$ 个询问的答案（模$59861874$之后）是 $q_i$，输出 $\prod\limits_{i=1}^{n} (i\times 114514+(q_i\oplus1919810)) \mod 998244353$。$|$ 表示按位或运算。

### 样例解释 自己写个暴力看看 ### 数据范围 $n\le 10^7,q\le 10^7,seed\le 10^8$ $l_i\le r_i$ $l_{i-1}\le l_i,r_{i-1}\le r_i$ ### 备注 $59861874=2\times 3\times 997\times 10007$，是合数 相当于数据是随机生成的，不过对于这个题影响不大 您当然可以注意到很多 $r$ 都等于 $n$，特殊处理掉后面几个的后缀和然后线段树