P8911 [RC-06] Minimum and Maximum
Background
Due to Luogu limitations, the testdata for this problem has been reduced. For the full set of testdata, please go to [InfOJ](http://119.27.163.117/contest/7/).
Description
Given a sequence of length $n$, $[a_1,a_2,\dots ,a_n]$.
There are $m$ queries. Each query gives four positive integers $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)$. You need to count how many intervals $[l,r]\ (1\le l\le r\le n)$ satisfy that, among $a_l,a_{l+1},\dots,a_r$, the maximum value lies in $[L_1,R_1]$ and the minimum value lies in $[L_2,R_2]$.
The number of queries is very large, so the queries are generated inside the program. Please read the code in the Hint section by yourself.
Input Format
The first line contains two positive integers $n,m$.
The next line contains $n$ positive integers $a_1\sim a_n$.
The next line contains three positive integers $p,q,seed$, which are the parameters of the data generator. You do not need to understand the detailed running process of the data generator. You only need to know that if the queries are generated correctly, then $L_1,R_1,L_2,R_2\in [p,q]$ must hold.
Output Format
Let the answer to the $i$-th query be $ans_i$. Output one line with one integer, the value of $\operatorname{xor}_{i=1}^m
(i\times ans_i)$.
Explanation/Hint
**Explanation for Sample 1**
For the five queries, $(L_1,R_1,L_2,R_2)$ are respectively $(1,5,1,5),(1,2,2,4),(3,4,2,2),(2,4,2,2),(2,5,2,5)$, and the answers are respectively $15,1,1,2,6$.
Output $(1\times 15)\ \mathrm{xor}\ (2\times 1)\ \mathrm{xor}\ (3\times 1)\ \mathrm{xor}\ (4\times 2)\ \mathrm{xor}\ (5\times 6)=24$.
**Sample Program**
Below is the sample program we provide. You can directly write your program based on it.
```cpp
#include
using namespace std;
typedef long long ll;
namespace Generator{
typedef unsigned long long ull;
typedef __uint128_t L;
ull seed;
int p,q;
struct FastMod {
ull b, m;
FastMod(ull b) : b(b), m(ull((L(1) > 64);
ull r = a - q * b; // can be proven that 0 = b ? r - b : r;
}
}F(2);
void init(){
cin>>p>>q>>seed;//read p,q,seed
assert(p!=q);
F=FastMod(q-p+1);
}
unsigned long long rd () {
seed ^= (seed > 7);
seed ^= (seed r1)swap(l1,r1);
if(l2>r2)swap(l2,r2);
}
}
int n,m,a[100005];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i