RMQ

Problem Description

You are given $n$ numbers $a_1, a_2, \dots, a_n$ and $q$ queries.

Each query gives two numbers $l, r$ and asks for the maximum value among $a_l, a_{l+1}, \dots, a_r$.

Input Format

The first line contains five numbers $n, q, A, B, C$ ($1\leq n\leq 10^6,\ 1\leq q\leq 10^7,\ 0\leq A, B, C < 2^{32}$).

To avoid excessively large input, $a_i$ and the queries are generated by the following code:

unsigned int A, B, C;
inline unsigned int rng61() {
    A ^= A << 16;
    A ^= A >> 5;
    A ^= A << 1;
    unsigned int t = A;
    A = B;
    B = C;
    C ^= t ^ A;
    return C;
}
int main(){
    scanf("%d%d%u%u%u", &n, &q, &A, &B, &C);
    for (int i = 1; i <= n; i++) {
        a[i] = rng61();
    }
    for (int i = 1; i <= q; i++) {
        unsigned int l = rng61() % n + 1, r = rng61() % n + 1;
        if (l > r) swap(l, r);
    }
}

Output Format

To avoid excessively large output, output the XOR sum of the answers to all the queries.

Sample Input

5 5 1 2 3

Sample Output

337927