You are given a 2D integer array $A$ of size $n \times m$ and $q$ queries of form $(a, b, c, d)$, calculate the sum of the subarray with upper-left corner $(a, b)$ and lower-right corner $(c, d)$.
### Input
- The first line contains 3 integers $n, m, q$.
- Each line in the next $n$ lines contains $m$ integers $A_{i, j}$.
- Each line in the next $q$ lines contains 4 integers $a, b, c, d$.
### Output
- Print $q$ line, $i^{th}$ line is the answer for query $i$.
### Constraints
- $1 \le n, m \le 1000$.
- $1 \le q \le 10^5$
- $1 \le A_i \le 10^9$.
### Example
Input:
```
2 3 2
1 4 3
2 2 3
1 1 2 2
2 1 2 3
```
Output:
```
9
7
```
