2D Prefix Sum

Problem Description

You are given an $n \times m$ matrix $a_{1,1}, a_{1,2}, \dots, a_{1,m}, \dots, a_{n,m}$ and $q$ queries.

Each query gives four numbers $x_1, y_1, x_2, y_2$ and asks for the value of $\sum_{i=x_1}^{x_2} \sum_{j=y_1}^{y_2} a_{i,j}$.

Input Format

The first line contains six integers $n, m, q, A, B, C$ ($1 \leq n, m \leq 2 \times 10^3, 1 \le q \leq 10^6, 0 \leq A, B, C < 2^{32}$).

To avoid overly large input, $a_{i,j}$ and the queries are generated by the following code.

int n, m, q;
unsigned int A, B, C;
long long a[N][N];
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%d%u%u%u", &n, &m, &q, &A, &B, &C);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            a[i][j] = rng61();
        }
    }
    for (int i = 1; i <= q; i++) {
        int x1 = rng61() % n + 1, x2 = rng61() % n + 1;
        int y1 = rng61() % m + 1, y2 = rng61() % m + 1;
        if (x1 > x2) swap(x1, x2);
        if (y1 > y2) swap(y1, y2);
        // perform the query
    }
}

Output Format

To avoid overly large output, output the XOR sum of all query answers.

Sample Input

5 5 10 1 2 3

Sample Output

1655687751