[I] 随机种子

题目背景

$\mathrm{Orz\ }$高一大爷$\mathrm{\ LSS,LSS\ tql}$!!!!!

题目描述

$\mathrm{LSS}$ 最喜欢随机了。他现在得到了一个长度为 $N$ 的随机种子序列 $S_i$,今天他准备用这几个随机种子生成序列。 他准备操作 $Q$ 次,每一次给出一个位置 $i$,表示以 $S_i$ 为序列开头第一个数,生成一个长度为 $K$ 的序列。他想到了一个随机生成的方法,对于上一个生成的数在种子序列(不是构造的序列)里的位置 $i$(一开始生成的数即为操作给出的位置 $i$),他在最初会给出 $a,b$,并进行如下运算: $$j=((i\oplus b)*a)\bmod n + 1$$ 然后将 $S_j$ 作为序列下一个数,然后重复此操作,直到构造完序列。对于每次操作,$\mathrm{LSS}$ 想知道构造出的序列的最大子段和(最大子段和不能不选)。

输入输出格式

输入格式


第一行,四个正整数 $N,Q,a,b$。 第二行,$N$ 个数,$S_i$。 接下来 $Q$ 行,每行两个正整数,$pos,K$,表示序列开头的数在种子序列中的位置,和需要构造的序列的长度。

输出格式


共 $Q$ 行,每个操作构造的序列的最大子段和。

输入输出样例

输入样例 #1

5 4 2 3
-2 4 2 -5 3
2 3
3 4
5 7
1 9

输出样例 #1

6
5
9
11

说明

$30$%的数据,$\mathrm{LSS}$ 想先试试随机的效果,$N,Q,K \le 5000$。 $100$%的数据,$\mathrm{LSS}$ 开始疯狂地构造,$N,Q \le 3\times 10^5$ 且 $a,b,K,\lvert S_i\rvert \le 10^9$。 时限:$2.5s$ 建议使用快速读入优化。