Sub-grid Sum Queries

You are given a grid of integers with n rows and m columns. Your task is to answer several queries, each asking for the sum of a sub-grid defined by its top-left and bottom-right coordinates.

To efficiently answer the queries, you should first preprocess the grid by computing a prefix sum matrix prefix where:

$$\text{prefix}[i][j] = grid[i-1][j-1] + \text{prefix}[i-1][j] + \text{prefix}[i][j-1] - \text{prefix}[i-1][j-1] $$

For each query given by coordinates \( (x_1,y_1) \) and \( (x_2,y_2) \) (using 1-indexing), the sum of the sub-grid is computed as:

$$S = \text{prefix}[x_2][y_2] - \text{prefix}[x_1-1][y_2] - \text{prefix}[x_2][y_1-1] + \text{prefix}[x_1-1][y_1-1] $$

Implement the solution so that it reads input from stdin and writes the results to stdout.

inputFormat

The input is given in the following format:

 n m
 row1
 row2
 ...
 row_n
 q
 x1 y1 x2 y2
 x1 y1 x2 y2
 ... (q queries)

where:

• n and m are the number of rows and columns of the grid respectively.
• Each of the next n lines contains m integers representing a row of the grid.
• q is the number of queries.
• Each query consists of 4 integers: x1 y1 x2 y2, representing the top-left and bottom-right coordinates of the sub-grid (1-indexed).

outputFormat

For each query, output a single integer on a new line which is the sum of integers in the specified sub-grid.

## sample

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

12
28

</p>