120002 - 二维前缀和

通过次数

8

提交次数

14

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

输入一个n 行m 列的整数矩阵,再输入q 个询问,每个询问包含四个整数x1, y1, x2, y2 ,表示一个 
子矩阵的左上角坐标和右下角坐标。对于每个询问输出子矩阵中所有数的和。

输入

第一行包含三个整数n,m,q 
接下来n 行,每行包含m 个整数,表示整数矩阵。 
接下来q 行,每行包含四个整数x1, y1, x2, y2 ,表示一组询问。

数据范围:

1 ≤ n, m ≤ 1000 
1 ≤ q ≤ 200000 
1 ≤ x1 ≤ x2 ≤ n 
1 ≤ y1 ≤ y2 ≤ m 
−1000 ≤ 矩阵内元素的值 ≤ 1000

输出

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

样例

输入

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