题目描述

给定一个 n x m 的矩阵 a，其中每个元素为一个整数。你需要支持 q 次查询，每次查询一个矩阵子区域的和。每次查询给定一个子矩阵的左上角 (x1, y1) 和右下角 (x2, y2)，请计算并输出该子矩阵中所有元素的和。

输入格式

第一行包含两个整数 n 和 m，表示矩阵的行数和列数。

接下来 n 行，每行包含 m 个整数，表示矩阵的每一行。

接下来一个整数 q，表示查询次数。

接下来 q 行，每行包含四个整数 x1, y1, x2, y2，表示查询的子矩阵的左上角和右下角的坐标。

输出格式

对于每次查询，输出一个整数，表示该子矩阵中所有元素的和。

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

12
28

样例解释

• 对于第一个查询，查询的是从 $(1, 1)$ 到 $(2, 2)$ 的子矩阵，其元素为：$1 + 2 + 4 + 5 = 12$
• 对于第二个查询，查询的是从 $(2, 2)$ 到 $(3, 3)$ 的子矩阵，其元素为：$5 + 6 + 8 + 9 = 28$

数据范围

• 对于 $50\%$ 的数据：$n, m <= 1000，q <= 1000$。
• 对于 $100\%$ 的数据：$n, m <= 1000，q <= 10000$。
• 输入数据保证 $1 <= x1 <= x2 <= n$ 且 $1 <= y1 <= y2 <= m$。