题目描述

我们有一个 $n$ 行 $m$ 列的由整数 $a_i$ 构成的矩阵。现在，有一些查询，每个查询提供四个整数 $x_1, y_1, x_2,$ 和 $y_2，$ 它们表示一个子矩阵的左上角和右下角坐标。你的任务是计算并输出这些子矩阵中所有数字的和。”

输入格式

第一行包含三个整数 $n，m，q。$

接下来 $n$ 行，每行包含 $m$ 个整数，表示整数矩阵。

接下来 $q$ 行，每行包含四个整数 $x_1, y_1, x_2, y_2$ 表示一组询问。

输出格式

共 $q$ 行，每行输出一个询问的结果。

数据范围

$1 ≤ n , m ≤ 1000.$

$1 ≤ q ≤ 500000.$

$1 ≤ x1 ≤ x2 ≤ n.$

$1 ≤ y1 ≤ y2 ≤ m.$

$−100 ≤ a_i ≤ 100.$

输入样例：

3 3 2
1 1 1
1 1 1
1 1 1
1 1 1 1
1 1 2 2

输出样例：

1
4