二维前缀和

题目描述

给一个 $n\times m$ 的矩阵 $a_{1, 1}, a_{1, 2}, \dots, a_{1, m}, \dots, a_{n, m}$ 和 $q$ 个询问。

每次询问给出四个数 $x_1, y_1, x_2, y_2$，求 $$\sum_{i=x_1}^{x_2} \sum_{j=y_1}^{y_2} a_{i, j}$$ 的值。

输入格式

第一行六个整数 $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})$。

为了防止输入过大，$a_{i, j}$ 和询问用下面代码生成。

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);
        // 执行查询操作
    }
}

输出格式

为了防止输出过大，输出所有询问答案的异或和。

样例输入

5 5 10 1 2 3

样例输出

1655687751