Matrix Sub-matrix Sum Queries

You are given a 2D matrix of integers and a set of queries. Each query defines a submatrix by specifying its top-left and bottom-right coordinates (using 1-indexing). Your task is to compute and output the sum of the elements within each specified submatrix efficiently.

To solve this problem efficiently, you may use a prefix sum approach. The prefix sum matrix P is computed using the formula:

$$P(i,j) = A(i,j) + P(i-1,j) + P(i,j-1) - P(i-1,j-1)$$

Once the prefix sum matrix is computed, the sum of any submatrix from \((x_1, y_1)\) to \((x_2, y_2)\) can be computed in constant time using:

$$\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)$$

inputFormat

The input is read from stdin and has the following format:

1. The first line contains two integers n and m representing the number of rows and columns of the matrix.
2. The next n lines each contain m space-separated integers representing the matrix elements.
3. The following line contains an integer q, the number of queries.
4. Each of the next q lines contains four space-separated integers: x1, y1, x2, y2, which represent the top-left and bottom-right coordinates of a submatrix (1-indexed).

outputFormat

For each query, output a single line containing one integer — the sum of the submatrix defined by the query.## sample

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

12
28