该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小A同学有着很强的计算能力，张老师为了检验小A同学的计算能力，写了一个n行m列的矩阵数列。

张老师问了小A同学k个问题，每个问题会先告知小A同学4个数x1, y1, x2, y2，表示这是矩阵中2个点的行列值。以这两个点为一个矩形的左上角和右下角，可以从矩阵中画出一个子矩阵，张老师请小A同学计算出这个子矩阵中所有数的和。

请你编程帮助张老师计算出结果。

输入格式

第一行包含三个整数n，m，k，分别表示矩阵的行数、列数和询问的次数。

接下来n行，每行包含m个整数，表示矩阵中的元素。

接下来k行，每行包含四个整数x1, y1, x2, y2，表示一组询问，其中(x1,y1)为子矩阵的左上角坐标，(x2,y2)为子矩阵的右下角坐标。

输出格式

共k行，每行输出一个询问的结果，即对应子矩阵中所有元素的和。

样例输入

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

样例输出

37
28
55
26

样例解释

1. 第一个询问：x1=1, y1=2, x2=2, y2=4
   对应的子矩阵包含元素：
   第1行第2-4列：1、6、7
   第2行第2-4列：10、4、9
   总和：1+6+7+10+4+9 = 37

2. 第二个询问：x1=2, y1=4, x2=3, y2=5
   对应的子矩阵包含元素：
   第2行第4-5列：9、9
   第3行第4-5列：3、7
   总和：9+9+3+7 = 28

3. 第三个询问：x1=2, y1=2, x2=3, y2=5
   对应的子矩阵包含元素：
   第2行第2-5列：10、4、9、9
   第3行第2-5列：6、7、3、7
   总和：10+4+9+9+6+7+3+7 = 55

4. 第四个询问：x1=1, y1=3, x2=2, y2=4
   对应的子矩阵包含元素：
   第1行第3-4列：6、7
   第2行第3-4列：4、9
   总和：6+7+4+9 = 26

数据范围

• 1 ≤ n, m ≤ 1000
• 1 ≤ k ≤ 200000
• 1 ≤ x1 ≤ x2 ≤ n
• 1 ≤ y1 ≤ y2 ≤ m
• 矩阵内元素的值范围：-1000 ≤ 元素值 ≤ 1000