Efficient Submatrix Sum Queries

You are given a 2D matrix with dimensions m x n and a series of queries. Each query specifies a submatrix by its top-left corner \( (r_1, c_1) \) and bottom-right corner \( (r_2, c_2) \) (with indices starting at 1). Your task is to compute the sum of all the numbers within that submatrix.

To solve this problem efficiently, you may preprocess the matrix to compute a 2D prefix sum array. The prefix sum \( P \) is defined as:

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

Then the sum of a submatrix defined by \( (r_1, c_1) \) and \( (r_2, c_2) \) can be computed in constant time using the formula:

[ S = P(r_2, c_2) - P(r_1-1, c_2) - P(r_2, c_1-1) + P(r_1-1, c_1-1) ]

Implement a solution that reads the input from standard input and outputs the answers to standard output, one per query.

inputFormat

The first line contains two integers \( m \) and \( n \), representing the number of rows and columns of the matrix.

The next \( m \) lines each contain \( n \) integers, representing the rows of the matrix.

The following line contains a single integer \( Q \), the number of queries.

Each of the next \( Q \) lines contains four integers \( r_1 \), \( c_1 \), \( r_2 \), \( c_2 \) describing a query for the sum of the submatrix from \( (r_1, c_1) \) to \( (r_2, c_2) \).

outputFormat

For each query, output a single line containing the sum of the elements in the specified submatrix.

## sample

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

12
28
45

</p>