数列前缀和 4

给定一个 $n$ 行 $m$ 列的矩阵 $a$，有 $q$ 次询问，每次给定 $(u, v)$ 和 $(x, y)$，请你求出： $$(\sum_{i = u}^x \sum_{j = v}^y a_{i,j}) \bmod 2^{64}$$ 也就是求出以 $(u, v)$ 为左上角、$(x,y)$ 为右下角的矩形元素和对 $2^{64}$ 取余数的结果。 ## Input **本题单测试点内有多组测试数据**。 输入的第一行是一个整数 $T$，表示数据组数。接下来依次给出每组数据的输入信息： 第一行三个整数，依次表示矩阵的行数 $n$ 和列数 $m$ 以及询问数 $q$。 接下来 $n$ 行，每行 $m$ 个整数。第 $i$ 行第 $j$ 个整数表示 $a_{i,j}$。 接下来 $q$ 行，每行四个整数，依次为 $u,v,x, y$，表示一组询问。 ## Output 为了避免输出过大，对于每组数据，请输出一行一个整数，表示本组数据的所有询问的答案的按位异或和。 [samples] ## Background 这次不是数列的问题了。 ## Note ### 样例 1 解释 对第一组数据，三次询问的答案依次为 $45,9,16$。其按位异或和为 $52$。 ### 数据规模与约定 对全部的测试点，保证 $1 \leq T \leq 10$，$1 \leq n, m \leq 10^3$，$1 \leq q \leq 10^6$，$0 \leq a_i < 2^{64}$，$1 \leq u \leq x \leq n$，$1 \leq v \leq y \leq m$。 数据保证 $\sum(n \times m) \leq 10^6$，$\sum q \leq 10^6$。即输入矩阵的总大小和询问总数均不超过 $10^6$。 ### 提示 如果你不知道什么是按位异或和，可以在你的代码里添加如下的函数： ```cpp template <class T> T getXorSum(T *begin, T *end) { T ret = 0; for (T *it = begin; it != end; ++it) ret ^= *it; return ret; } ``` 这一函数的作用是计算传入数组（包括 `std::vector`）某一左闭右开区间的按位异或和，返回值类型与传入数组的类型相同，调用方法与 `std::sort` 类似，例如，要求数组 $a$ 的 $a_1 \sim a_n$ 的按位异或和，则调用 `getXorSum(a + 1, a + 1 + n)`，求 $a_0 \sim a_{n - 1}$ 的按位异或和，则调用 `getXorSum(a, a + n)`。如果 $a$ 是 `std::vector`，则将上述调用代码里的 `a` 均改为 `a.begin()` 即可。