Description

学校有一个 $n \times m$ 的打卡墙。第 $i$ 行第 $j$ 列的格子上写着一个整数 $a_{i,j}$，表示该位置今天被同学们路过并顺手打卡的热度。

现在有 $q$ 个询问，每次给出一个矩形区域，你需要回答这个区域内所有格子的热度之和。

矩形区域由左上角 $(x_1,y_1)$ 和右下角 $(x_2,y_2)$ 描述。

Format

Input

第一行三个整数 $n,m,q(1 \le n,m \le 1000,1 \le q \le 2 \times 10^5)$。

接下来 $n$ 行，每行 $m$ 个整数，表示矩阵 $a(0 \le a_{i,j} \le 10^9)$。

接下来 $q$ 行，每行四个整数 $x_1,y_1,x_2,y_2(1 \le x_1 \le x_2 \le n,1 \le y_1 \le y_2 \le m)$，表示一次询问。

Output

对于每次询问，输出一行一个整数，表示矩形区域内的热度之和。

Samples

3 4 3
1 2 3 4
0 1 0 1
5 0 2 2
1 1 3 4
2 2 3 3
1 3 1 4

21
3
7

Note

样例说明：

第一次询问整个矩阵，和为 $21$。

第二次询问的区域和为 $3$。

第三次询问第一行第 $3$ 到第 $4$ 列，和为 $3+4=7$。