2D Prefix Sum Query

This problem involves computing submatrix sums efficiently using a 2D prefix sum matrix. Given an \(n \times m\) matrix and a number of queries, each describing a submatrix by its top-left corner \((r_1, c_1)\) and bottom-right corner \((r_2, c_2)\), you are required to preprocess the matrix into a prefix sum matrix and then answer each query using the following 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)$$

Here, \(P(i,j)\) represents the sum of all elements in the submatrix from \((1,1)\) to \((i,j)\). This preprocessing allows each query to be answered in constant time.

Make sure to carefully handle the array indices and consider the boundary conditions.

inputFormat

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

The next \(n\) lines each contain \(m\) space-separated integers representing the matrix elements.

The following line contains an integer \(q\), the number of queries.

Each of the next \(q\) lines contains four space-separated integers \(r_1, c_1, r_2, c_2\) specifying a submatrix query.

outputFormat

Output \(q\) lines, each containing a single integer which is the sum of the submatrix corresponding to that query.

## sample

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

12
28
45
16

</p>