LARGEST RECTANGLE

All submissions for this problem are available.
You are given an array of M*N elements each with nonnegative value. Now you will be given query denoted by 2 cordinates which will denote the topleft point of a subrectangle and bottomright point of the subrectangle. Now you need to find the sum of all the elements in the given subrectangle.
Input
The first line of the input contains two integers M and N indicating the number of rows and columns.The following M lines have N integers each which denotes the value at that particular cell.Line M+2 contains a single integer C indicating the number of subrectangles for which the total sum needs to be computed. Each of the following C lines (line M+2+1 ... M+2+C) each contain four integers x1, y1, x2 and y2 (with x1 ≤ x2 and y1 ≤ y2) and describes a rectangle. The rectangle has its top left corner at the tree in position (x1,y1) and its bottom right corner at the tree at position (x2,y2).
Output
Your output must contain C lines with one integer on each line. Line i must contain the total sum n the rectangle described on line M+2+i in the input.
Example
Input: 4 4 3 4 15 23 14 20 12 9 3 8 12 15 12 20 7 5 2 2 2 3 4 4 2 4 2 Output: 76 20
Author:  inoi_admin 
Tags  inoi_admin 
Date Added:  8112014 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA, PYTH, PYTH 3.6, PYP3 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 