Description

给出一个$n\times m$ 大小的二维数组$a[i][j]$.

$q$次查询，每次查询给出四个整数$x_{1},y_{1},x_{2},y_{2}$，要求输出$\sum_{i=x_{1}}^{x_{2}} \sum_{j=y_{1}}^{y_{2}} a[i][j]$.

Format

Input

第一行有三个整数$n$和$m$表示数组大小,$q$表示询问次数.

接下来输入$n$ 行，每行有$m$ 个整数表示$a[i][j]$ .

接下来有$q$ 行，每行有四个整数$x_{1},y_{1},x_{2},y_{2}$ ，表示询问$\sum_{i=x_{1}}^{x_{2}} \sum_{j=y_{1}}^{y_{2}} a[i][j]$.

.

.

.

Output

对于每组询问输出一个整数表示$\sum_{i=x_{1}}^{x_{2}} \sum_{j=y_{1}}^{y_{2}} a[i][j]$ .

Samples

3 4 2
1 2 2 4
5 4 7 5
9 5 3 2
1 1 1 1
2 2 3 4

1
26