All submissions for this problem are available.
Bhima and Arjun are playing a game. In the game, Bhima gave Arjun a grid A of size N × M, i.e. containing N rows and M columns.
Then Bhima asks Q queries to Arjun which Arjun has to answer correctly to win the game. In each query Bhima gives two coordinates (a, b) and (x, y) to Arjun. Arjun has to tell the sum of all the elements of the grid which lies within the bounds of the given coordinates, i.e. the sum of the elements within the coordinates (a, b) , (x, b), (a, y) and (x, y) inclusive. Can you help Arjun to win the game.
See example for clarification.
- The first line contains an integer T denoting the number of test cases.
- The first line of each test case contains two space separated integers N and M denoting the number of rows and columns in the grid respectively.
- N lines follow. The ith(1 <= i <= N) of these lines contain M space-separated integers the jth(1 <= j <= M) of which is the element A[i][j].
- The next line contains a single integer Q.
- Q lines follow. Each line contains 4 space separated integers a, b, x and y.
For each test case for every query output the required sum S in a new line.
- 1 ≤ T ≤ 100
- 1 ≤ N, M ≤ 1000
- 0 ≤ A[i][j] ≤ 108
- 1 ≤ Q ≤ 105
- 1 ≤ a ≤ x ≤ N
- 1 ≤ b ≤ y ≤ M
Note:Large IO files.
1 4 4 9 13 5 2 1 11 7 6 3 7 4 1 6 0 7 10 2 2 1 4 2 2 2 4 4
Example case 1:For the first query the required sum is that of 1, 11, 3, 7, 6, 0 which is 28.
|Tags||2-darray, encoding, horsbug98, horsbug98, prefix-sum, rangequeries, staticrangequeries|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS|
Fetching successful submissions