Submatrix Sum Queries

Given a matrix of size \(M \times N\), where each cell contains a positive integer, and \(Q\) queries, each specifying a submatrix by its top-left and bottom-right coordinates, your task is to compute the sum of the elements in the specified submatrix for each query.

For each query, output the sum on a separate line.

For example, consider the following matrix:

1 2 3
4 5 6
7 8 9

A query with coordinates (1, 1, 2, 2) will sum the elements at positions (1,1), (1,2), (2,1), and (2,2), hence computing \(5 + 6 + 8 + 9 = 28\).

inputFormat

The input is given via standard input (stdin) in the following format:

1. The first line contains two integers \(M\) and \(N\), separated by a space, representing the number of rows and columns of the matrix respectively.
2. The next \(M\) lines each contain \(N\) space-separated integers defining the matrix.
3. The next line contains an integer \(Q\), the number of queries.
4. Each of the following \(Q\) lines contains four integers \(r_1\), \(c_1\), \(r_2\), and \(c_2\), representing the top-left and bottom-right coordinates (0-indexed) of the submatrix to sum.

outputFormat

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

## sample

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

28
12

</p>