Description
(modifyied by predix sum)
One day, the government want to know the total valuation of the land in rectangular area. As the member of the government, you decided to pick up this project and develop an query system. The example show below:
First, the government will give you each land's valuation with specific size
Second, the government will give two point (top-left point and bottom-right point), and you need to compute the valuaiton of the land with specific area
ex1: (2,2) (3,3) ==> the valuation of land is 10 + 20 + 4 + 6 = 40
ex2: (1,1) (2,2) ==> the valuation of land is 10 + 20 + 5 + 10 = 45
ex3: (1,3) (3,3) ==> the valuation of land is 30 + 20 + 6 = 56
Hint : If you get TLE for last two testcases, you should think how to decrease some redundant operations for calculations (you can try to expand 1D prefix sum to 2D prefix sum)
Note that: If you are using visual studio, add #pragma warning(disable:4996) in the first line so that you can use scanf on your local machine.
Input
M N
S11 S12 . .. S1N
...
SM1 SM2 ...SMN
T
pma_1 pna_1 pmb_1 pn b_1
pma_1 pna_2 pmb_2 pn b_2
....
pma_T pna_T pmb_T pn b_T
pm1_1 pn1_1 pm2_1 pn 2_1
M : the row size ( 2 < M < 1000)
N: the column size (2 < N < 1000)
Sij: the element in the 2D array (0 <= Sij < 100)
T : the times of query (2 <= T < 5000)
pma_i pna_i pmb_i pnb_i : the top-left point and bottom-right point
( 1 <= pma_i <= pmb_i <= M)
( 1 <= pna_i <= pnb_i <= N)
Output
Compute the valuaiton of specific land area (followed by a newline character at the end of each output answer).