Submatrix Sum Queries using Prefix Sum Matrix

You are given T test cases. For each test case, you are given a 2D matrix of integers with dimensions N × M. After the matrix, an integer Q is provided representing the number of queries. Each query consists of four integers: r1, c1, r2, c2, which describe the top-left and bottom-right corners of a submatrix (1-indexed).

Your task is to compute the sum of the submatrix for each query. To achieve this efficiently, you may use the prefix sum technique. The prefix sum matrix P is defined as follows:

$$P[i][j] = matrix[i-1][j-1] + P[i-1][j] + P[i][j-1] - P[i-1][j-1]$$

Using the prefix sum matrix, the sum for a submatrix from (r1, c1) to (r2, c2) can be computed in constant time by:

$$sum = P[r2][c2] - P[r1-1][c2] - P[r2][c1-1] + P[r1-1][c1-1]$$

Implement a program that reads input from stdin and writes the results for each query to stdout.

inputFormat

The first line contains an integer T, the number of test cases. Each test case is described as follows:

• The first line contains two integers N and M, the dimensions of the matrix.
• The next N lines each contain M integers representing the matrix rows.
• The next line contains an integer Q, the number of queries.
• The following Q lines each contain four integers: r1, c1, r2, c2, where (r1, c1) is the top-left and (r2, c2) is the bottom-right coordinate of the submatrix to query.

All input is provided through stdin.

outputFormat

For each query, output the sum of the elements in the specified submatrix on a new line. The order of outputs should match the order of the queries as they appear in the input. All output should be written to stdout.

## sample

4
3 3
1 2 3
4 5 6
7 8 9
2
1 1 2 2
2 2 3 3
1 1
5
1
1 1 1 1
4 4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
2
1 1 2 2
3 3 4 4
3 3
1 1 1
1 1 1
1 1 1
1
1 1 3 3

12
28
5
14
54
9

</p>