The sales data is now a full grid — rows are branches, columns are days — and Shuvo needs fast answers to "what were total sales in branches R1-R2 during days C1-C2?" for many such rectangular queries. Given an N×M matrix and Q queries, each defining a rectangular submatrix by its top-left and bottom-right corners, print the sum of all elements in that submatrix. Precompute a 2D prefix sum so each query is O(1).
Input
Line1: N M. Next N lines: M integers each. Line: Q. Next Q lines: r1 c1 r2 c2 (1-indexed).
Output
Q lines: sum of the submatrix for each query.
Constraints
1 ≤ N,M ≤ 1000, 1 ≤ Q ≤ 10^5
Sample Input
3 3 1 2 3 4 5 6 7 8 9 1 1 1 2 2
Sample Output
12
main.c
Loading editor…
Write C, then Run (custom I/O) or Submit (sample tests). ⌘/Ctrl+Enter submits.