Submatrix Sum Queries

You are given a 2D grid (matrix) of integers with n rows and m columns. You are then asked to answer q queries. Each query provides the coordinates of the top-left and bottom-right corners of a submatrix, and your task is to compute the sum of the elements inside that submatrix.

To efficiently process the queries, you can use a prefix sum matrix. The prefix sum matrix P is defined as:

$$P[i][j] = \sum_{a=1}^{i}\sum_{b=1}^{j} M[a][b]$$

Using this matrix, the sum of any submatrix defined by the corners \((r_1, c_1)\) and \((r_2, c_2)\) can be calculated in constant time using the formula:

$$\text{Sum} = P[r_2][c_2] - P[r_1-1][c_2] - P[r_2][c_1-1] + P[r_1-1][c_1-1] $$

Implement a program that reads the matrix and a series of queries from standard input and writes the result of each query to standard output, one per line.

inputFormat

The first line of input contains three integers n, m, and q — the number of rows, the number of columns of the matrix, and the number of queries respectively.

The next n lines each contain m space-separated integers representing the matrix.

Each of the following q lines contains four integers r1, c1, r2, and c2 where:

• (r1, c1) are the 1-indexed coordinates of the top-left corner of the submatrix,
• (r2, c2) are the 1-indexed coordinates of the bottom-right corner of the submatrix.

outputFormat

For each query, output a single integer which is the sum of the specified submatrix. Each result should be printed on a new line.

## sample

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

12
28
45

</p>