B3693 数列前缀和 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}$ 取余数的结果。

无

无

### 样例 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 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()` 即可。