Matrix Range Query

You are given an 'N * M' matrix 'GRID'. You are also given 'Q' queries. Your task is to find the sum of the rectangular submatrix defined by the upper left corner and lower right corner for each query.

All indexes are 0 based.

Example:

'GRID' = [ [1, 2, 3],
           [4, 5, 6],
           [7, 8, 9] ]

'Q' = 1, left corner = (1, 1), right corner = (2, 2)
submatrix = [ [5, 6],
            [8, 9] ]   

Answer = 28

Input Format:

The first line of input contains an integer 'T’ denoting the number of test cases to run. Then the test case follows.

The first line of each test case contains three space-separated integers ‘N’, ‘M’, ‘Q’ number of rows and number of columns in 'GRID' and number of queries. 

Then ‘N’ lines follow. Each of the lines contains ‘M’ space-separated integers denoting the elements of the matrix 'GRID'.

Then ‘Q’ lines follow. Each of the lines contains four space-separated integers ‘X1’, ‘Y1’, ‘X2’, ‘Y2’ where (‘X1’, ‘Y1’) is an upper left corner. (‘X2’, ‘Y2’) is the lower right corner.

Output Format:

For each test case, return the array that contains sum of elements in the submatrix defined by the upper left and lower right corner for each query.

Note:

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N, M <= 10^3
-10^4 <= GRID[i][j] <= 10^4

Time Limit: 1 sec