{"raw_statement":[{"iden":"background","content":"受洛谷限制，本题数据有所删减。评测全套数据请到 [InfOJ](http://119.27.163.117/contest/7/)。"},{"iden":"statement","content":"给定长度为 $n$ 的序列 $[a_1,a_2,\\dots ,a_n]$。\n\n$m$ 次询问，每次给出四个正整数 $L_1,R_1,L_2,R_2\\ (1\\le L_1\\le R_1\\le 4000,1\\le L_2\\le R_2\\le 4000)$，问有多少个区间 $[l,r]\\ (1\\le l\\le r\\le n)$ 满足 $a_l,a_{l+1},\\dots,a_r$ 中的最大值属于 $[L_1,R_1]$、最小值属于 $[L_2,R_2]$。\n\n询问次数很大，所以询问是在程序内生成的。请自行阅读提示说明一栏的代码。"},{"iden":"input","content":"第一行两个正整数 $n,m$。\n\n接下来一行 $n$ 个正整数 $a_1\\sim a_n$。\n\n接下来一行三个正整数 $p,q,seed$，为数据生成器的参数。你不需要理解数据生成器具体的运行过程，你只需要知道，如果正确生成了询问的话，一定有 $L_1,R_1,L_2,R_2\\in [p,q]$。"},{"iden":"output","content":"设第 $i$ 个询问的答案为 $ans_i$。输出一行一个整数，为 $\\operatorname{xor}_{i=1}^m \n(i\\times ans_i)$ 的值。"},{"iden":"note","content":"**样例 1 解释**\n\n五次询问的 $(L_1,R_1,L_2,R_2)$ 分别为 $(1,5,1,5),(1,2,2,4),(3,4,2,2),(2,4,2,2),(2,5,2,5)$，答案分别为 $15,1,1,2,6$。\n\n输出 $(1\\times 15)\\ \\mathrm{xor}\\ (2\\times 1)\\ \\mathrm{xor}\\ (3\\times 1)\\ \\mathrm{xor}\\ (4\\times 2)\\ \\mathrm{xor}\\ (5\\times 6)=24$。\n\n**样例程序**\n\n下面是我们提供的样例程序，你可以直接以其为基础编写你的程序。\n\n```cpp\n#include<bits/stdc++.h>\nusing namespace std;\ntypedef long long ll;\nnamespace Generator{\ntypedef unsigned long long ull;\ntypedef __uint128_t L;\null seed;\nint p,q;\nstruct FastMod {\n    ull b, m;\n    FastMod(ull b) : b(b), m(ull((L(1) << 64) / b)) {}\n    ull reduce(ull a) {\n        ull q = (ull)((L(m) * a) >> 64);\n        ull r = a - q * b; // can be proven that 0 <= r < 2*b\n        return r >= b ? r - b : r;\n    }\n}F(2);\nvoid init(){\n\tcin>>p>>q>>seed;//读入 p,q,seed \n\tassert(p!=q);\n\tF=FastMod(q-p+1);\n}\nunsigned long long rd () {\n\tseed ^= (seed << 13);\n\tseed ^= (seed >> 7);\n\tseed ^= (seed << 17);\n\treturn seed;\n}\nvoid getlr(int &l1,int &r1,int &l2,int &r2){\n\t//将 l1,r1,l2,r2 作为参数传入，即可得到一组询问 \n\tl1=F.reduce(rd())+p;\n\tr1=F.reduce(rd())+p;\n\tl2=F.reduce(rd())+p;\n\tr2=F.reduce(rd())+p;\n\tif(l1>r1)swap(l1,r1);\n\tif(l2>r2)swap(l2,r2);\n}\n\n}\nint n,m,a[100005];\nint main(){\n\tscanf(\"%d%d\",&n,&m);\n\tfor(int i=1;i<=n;i++)scanf(\"%d\",&a[i]);\n\tGenerator::init();\n\tlong long xorsum=0;\n\tfor(int i=1,l1,r1,l2,r2;i<=m;i++){\n\t\tGenerator::getlr(l1,r1,l2,r2);\n\t\tlong long ans=/*ans保存你的答案*/;\n\t\txorsum^=ans*i;\n\t}\n\tcout<<xorsum;\n}\n```\n\n**数据范围**\n\n本题有四个子任务。子任务一时间限制 $0.5$ 秒，其它子任务时间限制 $5$ 秒。\n\n所有数据均满足：$1\\le n\\le 10^5$，$1\\le m\\le 2\\times 10^7$，$1\\le a_i\\le 4000$，$1\\le p\\lt q\\le 4000$，$0\\le seed\\lt 2^{64}$。\n\n- 子任务 $1$（$5$ 分）：$n,m,a_i,q\\le 10$。\n- 子任务 $2$（$20$ 分）：$n\\le 10^4$。\n- 子任务 $3$（$20$ 分）：$a_i,q\\le 10$。\n- 子任务 $4$（$55$ 分）：无特殊限制。"}],"translated_statement":null,"sample_group":[["5 5\n2 4 1 3 5\n1 5 1145141919810","24"],["10 20000000\n1 3 4 10 5 5 2 7 10 7\n1 10 23333333333333333","548722417"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}