Subgrid Sum Query

You are given a matrix (grid) with R rows and C columns. You have to answer K queries. Each query gives you four integers r1, c1, r2, and c2 representing the top-left and bottom-right coordinates of a subgrid (using 1-based indexing).

Your task is to calculate the sum of all elements within the specified subgrid for each query. An efficient way to solve this problem is to precompute the prefix sum matrix, where the sum over any subgrid can be computed using the formula:

$$ \text{sum} = PS[r2][c2] - PS[r1-1][c2] - PS[r2][c1-1] + PS[r1-1][c1-1] $$

Make sure to use proper input parsing from stdin and output the result for each query on a new line to stdout.

inputFormat

The first line contains three space-separated integers: R, C, and K, representing the number of rows, columns, and queries respectively.

The next R lines each contain C space-separated integers denoting the grid.

Then, the next K lines each contain four space-separated integers r1, c1, r2, and c2 which define a query for the subgrid.

outputFormat

For each query, output the sum of the numbers in the specified subgrid on a new line.

## sample

3 3 2
1 2 3
4 5 6
7 8 9
1 1 2 2
2 2 3 3

12
28

</p>