题目描述

有一个 $n\times m$ 的整数棋盘，第 $i$ 行第 $j$ 列的权值为 $a_{i,j}$。

现在有 $q$ 次询问。每次给出一个左上角 $(x_1,y_1)$ 和右下角 $(x_2,y_2)$，求这个矩形内所有格子的权值之和。

输入格式

第一行输入三个整数 $n,m,q$。

接下来 $n$ 行，每行输入 $m$ 个整数，表示棋盘权值。

接下来 $q$ 行，每行输入四个整数 $x_1,y_1,x_2,y_2$。

输出格式

每个询问输出一行矩形权值和。

样例

3 4 3
1 2 3 4
5 6 7 8
9 10 11 12
1 1 2 2
2 2 3 4
1 3 3 3

14
54
21

数据规模与约定

• $1\le n,m\le 1000$，且 $n\times m\le 10^6$；
• $1\le q\le 2\times 10^5$；
• $|a_{i,j}|\le 10^9$；
• $1\le x_1\le x_2\le n$，$1\le y_1\le y_2\le m$。

答案可能超过 int 范围。