问题描述

给定一个 $n\times m$ 大小的矩阵 $A$。

给定 $q$ 组查询，每次查询为给定 $4$ 个正整数 $x_1,y_1,x_2,y_2$，你需要输出 $\sum_{i=x_1}^{x_2}\sum_{j=y_1}^{y_2} A_{i,j}$ 的值。

输入格式

第一行输入 $3$ 个正整数 $n,m,q$。（$1\le n,m\le 10^3,1\le q\le 10^5$）

接下来 $n$ 行每行输入 $m$ 个整数，表示 $A_{i,j}$。$(-10^3\le A_{i,j}\le 10^3,1\le i\le n,1\le j\le m)$

接下来 $q$ 行，每行输入 $4$ 个正整数 $x_1,y_1,x_2,y_2$。$(1\le x_1\le x_2\le n,1\le y_1\le y_2\le m)$

输出格式

对于每次查询，输出一个整数，表示查询的子矩阵的和。

样例输入

3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4

样例输出

17
27
21