区域能量（area）

题目描述

$\text{DAMON THRONE}$ 的训练场可以看成一个 $n$ 行 $m$ 列的方格矩阵。

第 $i$ 行第 $j$ 列的方格中有一个能量值 $a_{i,j}$。

现在有 $q$ 次查询。每次查询给出四个整数 $x_1,y_1,x_2,y_2$，表示一个矩形区域：

• 左上角为 $(x_1,y_1)$；
• 右下角为 $(x_2,y_2)$。

请你计算这个矩形区域中所有方格的能量值之和。

输入格式

第一行包含三个整数 $n,m,q$，分别表示矩阵的行数、列数和查询次数。

接下来 $n$ 行，每行包含 $m$ 个整数，第 $i$ 行第 $j$ 个整数为 $a_{i,j}$，表示对应方格的能量值。

接下来 $q$ 行，每行包含四个整数 $x_1,y_1,x_2,y_2$，表示一次矩形区域查询。

输出格式

对于每次查询，输出一行一个整数，表示对应矩形区域的能量值总和。

输入输出样例 #1

输入 #1

4 5 3
1 2 3 4 5
5 4 3 2 1
2 2 2 2 2
1 3 5 7 9
1 1 2 3
2 2 4 5
3 1 3 5

输出 #1

18
42
10

样例解释 #1

第 $1$ 次查询的区域为：

$$\begin{matrix} 1&2&3\\ 5&4&3 \end{matrix}$$

能量总和为：

$$1+2+3+5+4+3=18$$

第 $2$ 次查询的区域为：

$$\begin{matrix} 4&3&2&1\\ 2&2&2&2\\ 3&5&7&9 \end{matrix} $$

能量总和为：

$$42$$

输入输出样例 #2

输入 #2

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

输出 #2

29
0
4
9

数据范围与约定

对于所有测试数据，保证：

$$1\le n,m\le1000,\quad 1\le n\times m\le10^6 ,\quad 1\le q\le2\times10^5 ,\quad -10^9\le a_{i,j}\le10^9,\quad 1\le x_1\le x_2\le n,\quad 1\le y_1\le y_2\le m $$

测试点	分值	$n,m$	$q$	特殊性质
$1\sim2$	$20$	$\le20$	$\le100$	无
$3\sim4$		$\le100$	$\le1000$	$\text{A}$
$5\sim6$		$\le1000$	$\le10^5$	$\text{B}$
$7\sim8$			$\le2\times10^5$	$\text{C}$
$9\sim10$				无

特殊性质 $\text{A}$：保证所有查询满足 $x_1=x_2$。

特殊性质 $\text{B}$：保证所有能量值均为非负数。

特殊性质 $\text{C}$：保证所有查询满足 $x_1=1$ 且 $y_1=1$。