围栏巡检：边界和

故事背景

农场的地块四周有围栏，巡检员只需关注每块矩形地的“边界”产量是否异常。为此，他希望快速得到任意矩形区域边界上所有格子的产量之和。

题目描述

给定一个 n×m 的整数矩阵 a，有 q 次询问。每次给出矩形 (x1, y1) 到 (x2, y2)（1 基，x1 ≤ x2，y1 ≤ y2）。

请输出该矩形“边界”上所有格子的元素之和。若矩形只有一行或一列，则边界即为整个矩形。

输入格式

• 第一行包含三个整数 n、m、q。
• 接下来 n 行，每行 m 个整数，表示矩阵 a。
• 接下来 q 行，每行四个整数 x1、y1、x2、y2。

输出格式

输出 q 行，每行一个整数，表示对应矩形的边界和。

输入输出样例 #1

输入 #1

3 4 3
1 2 3 4
5 6 7 8
9 10 11 12
1 1 3 4
2 2 3 3
2 1 2 4

输出 #1

65
34
26

样例解释 #1

第一问：矩形 (1,1)-(3,4) 的边界为外圈所有格子，总和为 78 减去内层 (2,2)-(2,3) 的 13，得到 65；第二问：矩形 (2,2)-(3,3) 的边界为 {6,7,10,11}，和为 34，2×2 无内层，四格皆边界；第三问：第二行整行边界就是该行总和 26。

说明/提示

• 数据范围示例：1 ≤ n,m ≤ 1000；1 ≤ q ≤ 2×10^5。
• 提示：可先用二维前缀和计算外层矩形和，再减去内层 (x1+1,y1+1)-(x2-1,y2-1) 的和（若内层存在），得到边界和。