#2468. 【模板】二维前缀和

【模板】二维前缀和

题目描述

给你一个 n 行 m 列的矩阵 A ,下标从1开始。

接下来有 q 次查询,每次查询输入 4 个参数 x1 , y1 , x2 , y2

请输出以 (x1, y1) 为左上角 , (x2,y2) 为右下角的子矩阵的和,

输入格式

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

接下来n行,每行m个整数,代表矩阵的元素

接下来q行,每行4个整数x1, y1, x2, y2,分别代表这次查询的参数

输出格式

输出q行,每行表示查询结果。

样例 #1

样例输入 #1

3 4 3
1 2 3 4
3 2 1 0
1 5 7 8
1 1 2 2
1 1 3 3
1 2 3 4

样例输出 #1

8
25
32

提示

1n,m10001≤n,m≤1000

1q1051≤q≤10^5

109a[i][j]109−10^9≤a[i][j]≤10^9

1x1x2n1≤x_1≤x_2≤n

1y1y2m1≤y _1≤y_2≤m