Orange的区间和II

题目描述

Orange有一个大小为 $n \times m$ 的矩阵 $A$，每次Orange会给你一个子矩阵的左上角和右下角两点，你需要求出由这两点所确定的子矩阵的所有元素之和。换句话说，Orange每次会给你 $(x, y)$ 和 $(x', y')$，你需要求出如下函数的值:

$$f(x, y, x', y') = \sum_{i=x}^{x'}\sum_{j=y}^{y'} A_{i;j}$$

输入格式

输入第一行包含3个整数 $n, m, T(n,m\leq 10^3; T \leq 10^5)$，其中 $n，m$ 表示给定矩阵的大小，$T$ 表示询问次数。 接下来 $n$ 行，每行包含 $m$ 个整数 $A_{i;j}(A_{i;j} \leq 10^9)$，表示给定的矩阵，之后的 $T$ 行，每行包含4个整数 $x,y,x',y'(1\leq x \leq x' \leq n; 1\leq y \leq y' \leq m)$，表示给定子矩阵的两个点。

输出格式

每个询问输出一行答案，表示该子矩阵的和。

样例 #1

样例输入 #1

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

样例输出 #1

12
11
24

提示

样例解释1:

第一次询问为$(1;1)(2;2)$，其表示的子矩阵为:

$$\left[\begin{array}{c} 1 & 2 \\ 4 & 5 \end{array}\right]$$

其元素之和为$1+2+4+5=12$，因此答案为12.