给定一个 m 行 n 列的整数矩阵 a,之后有 q 次查询。
每次查询给出四个整数 r_1、c_1、r_2、c_2,表示一个矩形区域的左上角坐标为 (r_1,c_1),右下角坐标为 (r_2,c_2)。请计算这个矩形区域内所有元素的和,包含矩形边界上的元素。
在所有查询过程中,矩阵中的元素不会被修改。
矩阵的行、列下标均从 1 开始。
第一行输入三个整数 m、n 和 q,分别表示矩阵的行数、列数和查询次数。
接下来 m 行,每行输入 n 个整数,第 i 行第 j 列的整数为 a_{i,j}。
接下来 q 行,每行输入四个整数 r_1、c_1、r_2、c_2,表示一次区域求和查询。
保证:
对于每次查询,输出一行整数,表示指定矩形区域的元素和。
5 5 3 3 0 1 4 2 5 6 3 2 1 1 2 0 1 5 4 1 0 1 7 1 0 3 0 5 3 2 5 4 2 2 3 3 2 3 3 5
8 11 12
2 3 4 1 -2 3 4 0 -5 1 1 2 3 1 2 1 3 2 3 2 3 1 2 2 2
1 1 -5 -2
第一次查询的区域为第 3 行至第 5 行、第 2 列至第 4 列,区域元素和为 2+0+1+1+0+1+0+3+0=8。
第二次查询的区域为第 2 行至第 3 行、第 2 列至第 3 列,区域元素和为 6+3+2+0=11。
第三次查询的区域为第 2 行至第 3 行、第 3 列至第 5 列,区域元素和为 3+2+1+0+1+5=12。
第 1 次查询整个矩阵,元素和为 1;第 2 次查询第一行第 2 列至第 3 列,元素和为 1;第 3 次只查询元素 a_{2,3},答案为 -5;第 4 次查询第二列的两个元素,答案为 -2。