题目描述

给定一个 $n$ 行 $m$ 列的矩阵 $a$，有 $q$ 次询问，每次给定 $(u, v)$ 和 $(x, y)$，请你求出：

$$\left(\sum_{i=u}^{x} \sum_{j=v}^{y} a_{i,j}\right) \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$，表示一组询问。

输出格式

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

数据范围

对全部的测试点，保证 $1 \le T \le 10$，$1 \le n, m \le 10^3$，$1 \le q \le 10^6$，$0 \le a_{i,j} < 2^{64}$，$1 \le u \le x \le n$，$1 \le v \le y \le m$。

数据保证 $\sum (n \times m) \le 10^6$，$\sum q \le 10^6$。

样例

输入样例 1

1
2 3 3
1 2 3
4 5 6
1 1 2 3
1 2 1 2
2 3 2 3

输出样例 1

17

提示

样例中三次询问的答案依次为 $21$、$2$、$6$，其按位异或和为 $21 \oplus 2 \oplus 6 = 17$。

用 unsigned long long 做二维前缀和即可天然完成 $\bmod 2^{64}$。