【模板】二维前缀和

题号：NC226333
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 给定一个由 $n$ 行 $m$ 列整数组成的矩阵 $\{a_{i,j}\}$ （下标均从 $1$ 开始）。
$\hspace{15pt}$ 现有 $q$ 次独立查询，第 $k$ 次查询给定四个整数 $x_1,y_1,x_2,y_2$ ，表示左上角坐标 $\left(x_1,y_1\right)$ 与右下角坐标 $\left(x_2,y_2\right)$ 满足 $1\leqq x_1\leqq x_2\leqq n$ 且 $1\leqq y_1\leqq y_2\leqq m$ 。
$\hspace{15pt}$ 请你计算该子矩阵中全部元素之和，记为

$\displaystyle S\bigl(x_1,y_1,x_2,y_2\bigr)=\sum_{i=x_1}^{x_2}\,\sum_{j=y_1}^{y_2} a_{i,j}$ 。

$\hspace{15pt}$ 你需要依次回答所有查询。

输入描述:

在一行上输入三个整数 ，依次表示矩阵的行数、列数与查询次数。
此后  行，每行输入  个整数 ，表示矩阵第  行的元素；共计  个整数。
此后  行，每行输入四个整数 ，所有变量均满足

。

输出描述:

对于每一次查询，在一行上输出一个整数，表示对应子矩阵元素之和。

示例1

输入

复制

输出

复制

8
25
32

说明

以第一组样例中的第二次查询  为例：
查询的子矩阵包含矩阵的左上  区域；
其内部所有元素之和为 ；
因此输出 。

备注:

读入数据可能很大，请注意读写时间。