题目描述

有一个 $n$ 行 $m$ 列的二维数组，左上角是第 $1$ 行第 $1$ 列，右下角是第 $n$ 行第 $m$ 列。其中第 $i$ 行第 $j$ 列的价值是 $a[i][j]$。

现在有 $Q$ 个询问，第 $i$ 个询问给出四个正整数 $x1,y1,x2,y2$，表示的意义是：以第 $x1$ 行第 $y1$ 列为左上角，第 $x2$ 行第 $y2$ 列为右下角的矩形，价值总和是多少？

输入格式

• 第一行，三个整数 $n,m,Q$，$1 \le n,m \le 1000$，$1 \le Q \le 100000$；
• 接下来是 $n$ 行 $m$ 列的二维数组，其中 $1 \le a[i][j] \le 1000$；
• 接下来有 $Q$ 行，第 $i$ 行是四个整数 $x1,y1,x2,y2$，$1 \le x1 \le x2 \le n$，$1 \le y1 \le y2 \le m$。

输出格式

共 $Q$ 行，每行一个整数，对应 $Q$ 个询问的结果。

样例

输入说明

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

输出说明

210
16
20