本题的IO量较大，为了避免IO效率影响算法速度的评判，我们采用一种特殊的方式输入数据

首先输入四个整数 n, m (1 ≤ n, m ≤ 10⁷) , k₁, k₂ (0 ≤ k₁, k₂ ≤ 2³² − 1) 分别是序列长度，询问次数，生成器种子。

再将下方代码中的 k₁, k₂ 设为输入的 k₁, k₂，请你自行用下方代码的方式来生成序列

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