Submatrix Sum Queries

You are given a matrix with N rows and M columns. You need to answer Q queries on this matrix. Each query contains four integers x1, y1, x2, y2 (with 1-indexed positions) that define a submatrix. The goal is to compute the sum of all elements within the submatrix whose top-left corner is at (x1, y1) and bottom-right corner is at (x2, y2).

To solve the problem efficiently, you can precompute a prefix sum matrix P where each element is defined as:

\(P(i,j) = \sum_{a=1}^{i} \sum_{b=1}^{j} mat[a][b]\)

Then, for a query defined by \( (x_1, y_1) \) and \( (x_2, y_2) \), the sum is:

\(S = P(x_2,y_2) - P(x_1-1,y_2) - P(x_2,y_1-1) + P(x_1-1,y_1-1)\)

It is guaranteed that the submatrix specified in each query is valid and non-empty.

inputFormat

The input consists of multiple lines:

1. The first line contains two integers N and M, the number of rows and columns of the matrix.
2. Then follow N lines, each containing M integers, representing the matrix.
3. The next line contains an integer Q, the number of queries.
4. Then follow Q lines, each containing four integers x1, y1, x2, y2 representing a query.

outputFormat

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

## sample

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

12
28

</p>