Prefix Sum Grid Queries

You are given a grid \(A\) of size \(n \times m\) containing integers. Your task is to answer \(q\) queries, where each query asks for the sum of a submatrix defined by its top-left coordinate \((x_1, y_1)\) and bottom-right coordinate \((x_2, y_2)\).

To solve the problem efficiently, you can precompute a prefix sum matrix \(S\) using the formula:

[ S_{i,j} = A_{i,j} + S_{i-1,j} + S_{i,j-1} - S_{i-1,j-1} ]

Here, indices are 1-indexed and the boundaries are defined as \(S_{i,0} = S_{0,j} = 0\). Once the prefix sum matrix is computed, you can answer any submatrix query \((x_1, y_1, x_2, y_2)\) by calculating:

[ \text{sum} = S_{x_2,y_2} - S_{x_1-1,y_2} - S_{x_2,y_1-1} + S_{x_1-1,y_1-1} ]

Implement the solution so that it reads from standard input and writes the answer for each query to standard output.

inputFormat

The input is given in the following format (read from stdin):

• The first line contains two integers (n) and (m) representing the number of rows and columns of the grid.
• The next (n) lines each contain (m) space-separated integers representing the grid elements.
• 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), (y_2), describing a query. The coordinates are 1-indexed.

outputFormat

For each query, output the sum of the submatrix (one per line) to stdout.## sample

3 3
1 2 4
8 16 32
64 128 256
2
1 1 2 2
2 2 3 3

27
432