Submatrix Sum Query

Given an (M \times M) integer matrix, you are required to answer (Q) queries. Each query specifies a submatrix by giving its upper left corner ((x_1,y_1)) and lower right corner ((x_2,y_2)). Your task is to compute the sum of all elements within the specified submatrix efficiently.

An efficient approach is to use a 2D prefix sum matrix (P), constructed via the formula:
$$ P[i][j] = matrix[i-1][j-1] + P[i-1][j] + P[i][j-1] - P[i-1][j-1] $$
For a submatrix defined by coordinates ((x_1,y_1)) and ((x_2,y_2)), the sum is computed as:
$$ \text{sum} = P[x_2][y_2] - P[x_1-1][y_2] - P[x_2][y_1-1] + P[x_1-1][y_1-1] $$
Note that the indices in the input are 1-indexed.

inputFormat

The first line contains an integer (M) representing the size of the matrix. The next (M) lines each contain (M) space-separated integers denoting the elements of the matrix. The following line contains an integer (Q), the number of queries. Each of the next (Q) lines contains four integers (x_1), (y_1), (x_2), and (y_2) describing a query.

outputFormat

Output (Q) lines; each line should contain a single integer which is the sum of the submatrix corresponding to that query.## sample

4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
2
1 1 2 2
2 2 4 4

14
99