Submatrix Sum Queries

You are given an (N \times M) matrix and (Q) queries. Each query consists of four integers (x_1, y_1, x_2, y_2) which represent the top-left and bottom-right coordinates of a submatrix (using 0-indexing). For each query, compute the sum of elements in the specified submatrix.

To solve this problem efficiently, you can precompute a prefix sum matrix (P) where

[ P[i][j] = \text{matrix}[i-1][j-1] + P[i-1][j] + P[i][j-1] - P[i-1][j-1] ]

for (1 \le i \le N) and (1 \le j \le M). Be careful to convert indices since the input uses 0-indexing. Use the prefix sum matrix to answer any query in O(1) time.

The input and output are read from stdin and written to stdout respectively.

inputFormat

The first line contains three integers (N), (M), and (Q), representing the number of rows, the number of columns, and the number of queries respectively. The next (N) lines each contain (M) integers representing the matrix. Each of the following (Q) lines contains four integers (x_1), (y_1), (x_2), (y_2) (0-indexed) defining the opposite corners of a submatrix.

outputFormat

For each query, output the sum of the elements in the specified submatrix on a new line.## sample

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

12
28