矩阵区域和查询

题目描述

给定一个 n × m 的二维整数矩阵 a，有 q 个查询。每个查询指定一个矩形区域，该区域由左上角坐标 (x1, y1) 和右下角坐标 (x2, y2) 确定。对于每个查询，你需要计算并输出该矩形区域内所有元素的和。

注意：矩阵的行和列索引从 1 开始。

输入格式

第一行包含三个整数 n, m, q，分别表示矩阵的行数、列数和查询数量。

接下来 n 行，每行包含 m 个整数，表示矩阵 a 的元素。矩阵元素的取值范围为 [0, 1000]。

接下来 q 行，每行包含四个整数 x1, y1, x2, y2，表示一个查询的矩形区域。

输出格式

输出 q 行，每行一个整数，表示对应查询的矩形区域内所有元素的和。

数据范围

• 1 ≤ n ≤ 2000
• 1 ≤ m ≤ 2000
• 1 ≤ q ≤ 10000
• 1 ≤ x1 ≤ x2 ≤ n
• 1 ≤ y1 ≤ y2 ≤ m
• 0 ≤ a[i][j] ≤ 1000

样例输入

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

样例输出

12
28
45