12047 - Summation of sub-matrices   

Status  |  Limits Submit

Description

This problem is more complex compared to other problems. It is recommended that you should try to solve the other problems first if you haven't read or finished them.

 

Note for submission: while TAs are designing this problem, we found that choosing the wrong compiler (C++xx) might cause an acceptable code to be judged as incorrect. So remember to choose the C compiler!

 

Given a 2D array Arr, find the sum of elements in a given range.

There will be multiple queries in this question.

 

Definition of the sum of elements in a given range X1, Y1, X2, Y2:

Sum = Σ(Arr[i][j]), X1 ≤ i ≤ X2, Y1 ≤ j ≤ Y2

This problem is an extended version of homework 12022 - prefix sum. You will need to use similar techniques to solve this problem.

Input

The first line contains 2 integers N, M that specify the matrix size.

For the next N lines, each of them contains M integers. The j-th integer in the i-th of these lines is Arr[i][j].

Then the next line (N+2-th line) contains an integer Q, meaning there will be Q queries.

Then for the next Q lines (each of them forms a query), each contains 4 integers X1, Y1, X2, Y2, indicating the range of the sub-matrix.

The array index is 1-based.

 

1 ≤ X1 ≤ X2 ≤ N, 1 ≤ Y1 ≤ Y2 ≤ M.

It is guaranteed that every element is less than 50 (0 ≤ Arr[i][j] ≤ 49).

 

Output

For each query, output one line containing an integer representing the sum of elements of the submatrix.

Sample Input  Download

Sample Output  Download

Tags




Discuss