Description

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

$q$次查询，每次查询给出两个整数$x,y$，要求输出$\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,y$ ，表示询问$\sum_{i=x_{1}}^{x_{2}} \sum_{j=y_{1}}^{y_{2}} a[i][j]$.

$1\le n,m\le 10^3$.

.$1\le a[i][j],q\le 10^5$.

.$1\le x\le n$.
$1\le y\le m$.

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
2 3

1
21