Matrix Query Using Prefix Sum

You are given a matrix consisting of N rows and M columns. Your task is to answer a number of queries, each asking for the sum of a subrectangle in the matrix.

To achieve efficient query answers, you are required to preprocess the matrix by constructing a prefix sum matrix PS where the formula is given in \( \text{PS}_{i,j} = matrix_{i,j} + \text{PS}_{i-1,j} + \text{PS}_{i,j-1} - \text{PS}_{i-1,j-1} \) with 1-indexed matrix positions.

After preprocessing, for each query defined by the top-left coordinate \((r_1, c_1)\) and bottom-right coordinate \((r_2, c_2)\), the answer can be computed using the formula:

[ \text{sum} = \text{PS}{r_2,c_2} - \text{PS}{r_1-1,c_2} - \text{PS}{r_2,c_1-1} + \text{PS}{r_1-1,c_1-1} ]

All indices are 1-based.

inputFormat

The first line of input contains two integers N and M representing the number of rows and columns respectively.

The next N lines each contain M space-separated integers representing the matrix.

The following line contains an integer Q representing the number of queries.

Each of the next Q lines contains four integers: r1 c1 r2 c2, which represent the top-left and bottom-right coordinates of the subrectangle.

outputFormat

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

## sample

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

12
45

</p>