题目背景

这次不是数列的问题了。

题目描述

给定一个 $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}$ 取余数的结果。

输入格式

本题单测试点内有多组测试数据。

输入的第一行是一个整数 $T$，表示数据组数。接下来依次给出每组数据的输入信息：

第一行三个整数，依次表示矩阵的行数 $n$ 和列数 $m$ 以及询问数 $q$。
接下来 $n$ 行，每行 $m$ 个整数。第 $i$ 行第 $j$ 个整数表示 $a_{i,j}$。
接下来 $q$ 行，每行四个整数，依次为 $u,v,x, y$，表示一组询问。

输出格式

为了避免输出过大，对于每组数据，请输出一行一个整数，表示本组数据的所有询问的答案的按位异或和。

2
3 3 3
1 2 3
4 5 6
7 8 9
1 1 3 3
2 1 2 2
1 2 2 3
2 2 1
1 3
4 6
2 2 2 2

52
6

提示

样例 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$。

提示

如果你不知道什么是按位异或和，可以在你的代码里添加如下的函数：

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() 即可。