Bernadette Rostenkowski-Wolowitz is running a large-scale lab experiment studying the growth of different bacterial cultures on a petri dish.In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of November 22nd
(this exercise will still be available for submission after that deadline, but without counting towards your grade)
[to understand the context of this problem, you should read the class #06 exercise sheet]
In this problem you should read your input from stdin using the input() function and you should print the requested output.
Bernadette Rostenkowski-Wolowitz is running a large-scale lab experiment studying the growth of different bacterial cultures on a petri dish.
The petri dish can be seen as n × m grid, where each cell contains an integer representing the measured bacterial activity at that location.
To analyze her results, Bernadette needs to quickly compute the total activity within several rectangular regions of the dish, each region specified by two corner coordinates.
Doing this manually for each region would take forever (and Bernadette has a baby to get home to), so she needs an efficient way to handle multiple queries.
Write a program that receives a matrix of list of n × m integers, and a list of q queries in the form of two corners of a subrectangle and prints the sum of all numbers in the respective subrectangle.
The first line of input contains two integer n m, the number number of columns and rows of the petri dish.
The following m lines each contain n integers, separated by a single space, representing the petri dish matrix.
The next line contains an integer q representing the number of queries that follow
The following q lines each contain four integers x1 y1 x2 y2, indicating that we want the summation of the rectangle with corners (x1, y1) and (x2, y2).
The following limits are guaranteed in all the test cases that will be given to your program:
| 1 ≤ n, m ≤ 250 | Number of columns and rows of the matrix | |
| 1 ≤ cell(i,j) ≤ 100 | Range of integers in the matrix | |
| 1 ≤ q ≤ 50 000 | Number of queries | |
| 1 ≤ x1 ≤ x2 ≤ n | Range of columns in each query | |
| 1 ≤ y1 ≤ y2 ≤ n | Range of rows in each query |
NOTE: the limits are high and you must have an efficient solution.
If your code in each query simply iterates through all cells of the subrectangle and sums, it will result in a Time Limit Exceeded.
| Example Input | Example Output |
4 3 2 1 3 5 4 7 1 3 8 2 9 2 4 1 2 2 3 1 1 4 3 2 2 2 2 2 2 4 2 |
21 47 7 11 |
Explanation of the input
The following diagram clarifies the coordinates of the matrix:
x
1 2 3 4
1 2 1 3 5
y 2 4 7 1 3
3 8 2 9 2
The first query has corners (1,2) and (2,3) with sum = 21:
2 1 3 5 4 7 1 3 8 2 9 2
The second query has corners (1,1) and (4,3) with sum = 47:
2 1 3 5 4 7 1 3 8 2 9 2
The third query has corners (2,2) and (2,2) with sum = 7:
2 1 3 5
4 7 1 3
8 2 9 2
The forth query has corners (2,2) and (4,2) with sum = 11:
2 1 3 5
4 7 1 3
8 2 9 2