【题目描述】

鲍勃是一个顽强的少年，继排序研究和数学研究遭遇困难之后，他意识到算法的研究不能停留在理论层面，必须要有扎实的编程技巧作为基础。于是他决定学习编程的知识。

鲍勃了解到，在编程中动态规划是非常重要的一个知识点。在他研究动态规划的时候遇到了这样一个问题：” 最大子段和问题”，这个问题是：给你一个序列，你需要找出其中的一个子段 (不一定非空) 使

这一段的和是序列的所有段中最大的。

鲍勃突发奇想：这个题能不能改成：多次询问每次给一个区间，找出来这个区间内的最大子段和?

可惜的是，这似乎不是一个容易的问题，鲍勃又来寻求你的帮助了。

【输入格式】

第一行一个 n(1 ≤ n ≤ 2 × 10^6 )，代表序列的长度

其后一行 n 个数字，代表原序列 A，下标从 1 ∼ n，|Ai | <= 10^3

其后一行一个 q(1 ≤ q ≤ 10^7 ), 代表询问的个数

其后输入一行两个整数 k1,k2(0 ≤ k1, k2 ≤ 2^32 − 1)，其作用下方会说明

由于本题的询问次数过多，为了避免 IO 时间影响算法效率，本题采用特殊的方法来读入询问。

将下方代码中的 k1,k2 设为输入的 k1,k2

unsigned k1,k2;

unsigned long long xorShift128Plus() {

unsigned long long k3 = k1, k4 = k2;

k1 = k4;

k3 ^= k3 << 23;

k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);

return k2 + k4;

}

请你用下方的方式生成询问的区间

for(int i=1;i<=m;i++){

l[i]=xorShift128Plus()%n+1;

r[i]=xorShift128Plus()%n+1;

if(l[i]>r[i]) swap(l[i],r[i]);

}

【输出格式】

为了避免输出数据过多影响算法速度，你只需要输出一行一个整数代表每次询问的答案的异或和。

【样例】

【提示】 

样例中，998244353 1000000007 作为 k1,k2, 当 n 等于 5 时产生的前两个区间为 [2,2],[3,5]。这两个区间的最大子段和分别为 0 和 7，所以异或和是 7

【数据范围与约束】