子序列

题目描述

给定一个长度为 $N$ 的序列 $A$。对于一个子序列，若任意两个在子序列中相邻的元素 $A_x,A_y (x < y)$ ,都满足 $A_x < A_y$,且原序列的区间 $[x,y)$ 中不存在严格大于 $A_x$ 的值，那么我们就说这个子序列是"贪心上升"的。

定义一个子序列的权值为子序列中所有元素的和，给定 $Q$ 次询问，每次询问给定一个区间 $[L,R]$ ,请你求出这个区间中权值最大的贪心上升子序列的权值是多少。

本题输入输出量过大，因此采用随机方式生成询问区间， 并且你只需要输出所有询问答案的异或和。部分测点要求强制在线，请注意阅读输入格式和输出格式。

输入格式

第一行输入 4 个正整数 $N,Q,T,S$ ,表示序列长度,询问数量，强制在线系数和随机参数。

接下来一行，输入 $N$ 个正整数，表示序列 $A$.

询问区间 $[L,R]$ 由以下方式生成:

namespace GenHelper {
  unsigned z1,z2,z3,z4,b;
  unsigned rand_()
  {
  b=((z1<<6)^z1)>>13;
  z1=((z1&4294967294U)<<18)^b;
  b=((z2<<2)^z2)>>27;
  z2=((z2&4294967288U)<<2)^b;
  b=((z3<<13)^z3)>>21;
  z3=((z3&4294967280U)<<7)^b;
  b=((z4<<3)^z4)>>12;
  z4=((z4&4294967168U)<<13)^b;
  return (z1^z2^z3^z4);
  }
}
void srand(unsigned x)
{using namespace GenHelper;
z1=x; z2=(~x)^0x233333333U; z3=x^0x1234598766U; z4=(~x)+51;}
int read()
{
  using namespace GenHelper;
  int a=rand_()&32767;
  int b=rand_()&32767;
  return a*32768+b;
}

你需要在你的程序中加入以上代码，并在输入 $S$ 后调用 srand(S);

每次询问时，使用以下方式得到区间 $[L,R]$ 的范围。

int L=(lastans*T+read())%n+1;
int R=(lastans*T+read())%n+1;
if(L>R) swap(L,R);

其中，$lastans$ 表示之前所有询问答案的异或和。一开始 $lastans = 0$.

输出格式

一行，输出一个非负整数，表示所有答案的异或和。

样例 #1

样例输入 #1

8 4 0 114514
6 5 7 3 8 4 5 7

样例输出 #1

21

样例 #2

样例输入 #2

10 5 1 1919810
3 2 3 0 8 5 7 2 6 9

样例输出 #2

6

提示

样例解释：

对于样例 1 的每个询问，$L,R$ 和这个询问的答案依次为：

1 1 6
5 8 16
2 4 12
3 6 15

对于样例 2 的每个询问， $L,R$ 和这个询问的答案依次为：

3 8 12
1 9 13
10 10 9
7 9 8
9 9 6

数据范围：

对于所有数据，保证满足 $0 \le a_i,S \le 10^9，T \in [0,1]$.