题目描述

在一个 $n$ 行 $m$ 列的整数矩阵 $A$ 里，每个格子都有一个整数。现在你需要处理 $q$ 次查询，每次查询会给出一个子矩阵的左上角坐标 $(x_1, y_1)$ 和右下角坐标 $(x_2, y_2)$，你要计算并输出这个子矩阵内所有元素的和。

输入格式

• 第一行包含三个整数 $n$、$m$ 和 $q$，分别表示矩阵的行数、列数以及查询的次数。
• 接下来的 $n$ 行，每行包含 $m$ 个整数，用来描述矩阵 $A$ 的元素。
• 之后的 $q$ 行，每行包含四个整数 $x_1$、$y_1$、$x_2$、$y_2$，代表一次查询中子矩阵的左上角和右下角坐标。

输出格式

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

数据范围

• $1 \leq n, m \leq 1000$
• $1 \leq q \leq 2*10^5$
• $1 \leq x_1 \leq x_2 \leq n$
• $1 \leq y_1 \leq y_2 \leq m$
• 矩阵内元素的绝对值不超过 $1000$

样例输入

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

样例输出

14
38

提示

本题适合使用二维前缀和的方法来解决。你可以先预处理出二维前缀和数组，然后利用这个数组在 $O(1)$ 的时间复杂度内完成每次查询。