Submatrix Sum Query using Prefix Sum

You are given a matrix and several queries. For each query, you need to compute the sum of the submatrix defined by its top-left and bottom-right corners. To achieve this efficiently, you are encouraged to use a prefix sum matrix.

The prefix sum matrix PS is defined with an extra row and column (all zeros), and the following recurrence holds for \(1 \le i \le n\) and \(1 \le j \le m\):

[ PS[i][j] = matrix[i-1][j-1] + PS[i-1][j] + PS[i][j-1] - PS[i-1][j-1] ]

Once the prefix sum matrix is computed, the sum of a submatrix from \( (r_1, c_1) \) to \( (r_2, c_2) \) (0-indexed) can be computed as:

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

Implement a program that reads the matrix and a set of queries from standard input, and writes the corresponding submatrix sums to standard output.

inputFormat

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

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

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

Each of the next \(Q\) lines contains four integers \(r_1\), \(c_1\), \(r_2\), \(c_2\) which specify the top-left and bottom-right corners of the submatrix (0-indexed).

outputFormat

For each query, output the sum of the elements in the specified submatrix on a new line.

## sample

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

12
28
45

</p>