农田产量统计

故事背景

一位农场主把农田划分成 n×m 的小格，每个格子记录当天的产量。他经常需要查询某一块矩形田地的总产量，以便安排运输与销售。如果每次都逐格相加，效率会很低。请你帮他高效地完成多次矩形区域求和。

题目描述

给定一个 n×m 的整数矩阵 a，接着有 q 次询问。每次询问给出一个矩形 (x1, y1) 到 (x2, y2)（1 ≤ x1 ≤ x2 ≤ n，1 ≤ y1 ≤ y2 ≤ m，均为 1 基下标），请输出该矩形内所有元素之和。

输入格式

• 第一行包含三个整数 n、m、q。
• 接下来 n 行，每行 m 个整数，表示矩阵 a 的元素。
• 接下来 q 行，每行四个整数 x1、y1、x2、y2，表示一次查询的矩形（含边界）。

输出格式

输出 q 行，每行一个整数，表示对应查询矩形内元素之和。

输入输出样例 #1

输入 #1

4 4 1
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
2 2 3 4

输出 #1

54

样例解释 #1

矩形 (2,2)-(3,4) 包含 {6,7,8,10,11,12}，总和为 54。

说明/提示

• 数据范围示例：1 ≤ n,m ≤ 1000；1 ≤ q ≤ 2×10^5；-10^9 ≤ a[i][j] ≤ 10^9。
• 建议使用 64 位整数类型（如 C++ 的 long long）保存和。
• 提示：可预处理二维前缀和 s，用 s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1] 常数时间回答查询。