Taco Submatrix Sums

You are given a matrix with n rows and m columns, and q queries. Each query specifies a submatrix by providing four integers a, b, c, and d (with 1-indexed positions) which represent the top‐left and bottom‐right coordinates of the submatrix respectively.

Your task is to calculate and output the sum of all the elements in each queried submatrix.

One efficient approach is to use a prefix sum matrix P, defined as:

$$P(i,j) = \sum_{x=1}^{i}\sum_{y=1}^{j} matrix[x][y] $$

Then, for each query, you can compute the sum of the submatrix (with top-left \((a,b)\) and bottom-right \((c,d)\)) using the formula:

$$S = P(c,d) - P(a-1,d) - P(c,b-1) + P(a-1,b-1)$$

Note that indices are 1-indexed in the input, so be sure to adjust your array indices appropriately if using 0-indexed arrays in your code.

inputFormat

The first line contains three integers n, m, and q separated by spaces, representing the number of rows, the number of columns of the matrix, and the number of queries, respectively.

The next n lines each contain m integers, where the j-th integer in the i-th line represents the element matrix[i][j].

The next q lines each contain four integers a, b, c, and d, representing a query to compute the sum of the submatrix from row a to row c and column b to column d.

outputFormat

For each query, output a single integer on a new line representing the sum of the submatrix defined by that query.

## sample

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

12
28

</p>