Rectangle Sum Queries

You are given a matrix of integers and a number of queries. For each query, you are asked to compute the sum of the elements within a rectangular submatrix defined by its top‐left and bottom‐right coordinates. To achieve an efficient solution, you may use a prefix sum (cumulative sum) technique.

The prefix sum matrix \(P\) is defined as:

[ P[i][j] = \sum_{a=0}^{i-1} \sum_{b=0}^{j-1} matrix[a][b] ]

Then, the sum of a submatrix with top-left \((r_1, c_1)\) and bottom-right \((r_2, c_2)\) (using 0-based indexing) can be computed as:

[ S = P[r_2+1][c_2+1] - P[r_1][c_2+1] - P[r_2+1][c_1] + P[r_1][c_1] ]

Your task is to implement a program that reads the matrix and queries from standard input, computes the sum for each query, and prints the results to standard output.

inputFormat

The input is read from stdin and has the following format:

• The first line contains two integers \(n\) and \(m\) denoting the number of rows and columns in the matrix.
• The next \(n\) lines each contain \(m\) integers, representing the rows of the matrix.
• The following line contains an integer \(q\) representing the number of queries.
• Each of the next \(q\) lines contains four integers \(r_1\), \(c_1\), \(r_2\), \(c_2\) (0-based indices), which define the top-left and bottom-right coordinates of the submatrix.

outputFormat

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

## sample

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

12
28

</p>