39 - 二维前缀和

通过次数

78

提交次数

218

时间限制 : 3 秒
内存限制 : 128 MB

JM有一个一个nm列的整数矩阵.

好奇的JM有q次询问,每个询问包含四个整数x_1, y_1, x_2, y_2,表示一个子矩阵的左上角坐标和右下角坐标。

对于每个询问输出子矩阵中所有数的和。

输入

第一行包含三个整数n,m,q

接下来n行,每行包含m个整数a_{ij},表示整数矩阵。

接下来q行,每行包含四个整数x_1, y_1, x_2, y_2,表示一组询问

输出

共q行,每行输出一个询问的结果。

样例

输入

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

输出

45
5

提示

数据规模

对于50\%的数据

1≤n,m≤100,1≤q≤2000

对于100\%的数据

1≤n,m≤1000,1≤q≤200000.

1≤x_1≤x_2≤n,1≤y_1≤y_2≤m,a_{ij}int范围内