小Z最近学习了最大子段和问题，这个问题是如何在一个序列中找出连续的一段，并且这一段的和最大。小Z经过学习，给出了这样的一个问题：
对于一个长度为n的序列，一共m次查询，每次给定一个区间 [li,ri] ，能否快速求出该区间内的最大子段和？
特别的，如果区间内元素都小于等于0，那么区间最大子段和视为0。可以理解为选了一个空的子段。
相信这种程度的问题，难不倒聪明的你

本题的IO量较大，为了避免IO效率影响算法速度的评判，我们采用一种特殊的方式输入数据
首先输入四个整数n,m(1≤n,m≤107),k1,k2(0≤k1,k2≤232−1)分别是序列长度，询问次数，生成器种子。
再将下方代码中的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<=n;i++){ a[i]=xorShift128Plus()%200-100; }
        

         

        

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

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]); }
        

        

         

        
        

         

        

为了避免输出的速度影响算法的判定，请你输出一行一个整数，代表每次询问的答案异或起来的值。

“卓见杯”18新利直播 第十五届程序设计大赛暨河南省高校邀请赛