Indian National Olympiad in Informatics

Related:

Online Programming Contest, 4-5 December, 2004

IARCS home > OLYMPIAD

Advanced Division

Problem 2: The Timber Auction, (K Narayan Kumar, CMI)

The GoC Timber Mafia is notorious for its deforestation activities in the forests near Siruseri. These activities have increased multifold after the death of the bandit who used to lord over these jungles. Having lost the battle to prevent the Mafia from illegally felling the teak trees in this forest, the government of Siruseri came up with a novel idea. Why not legalise the deforestation activity and at least make some money in the process? So the Government decided to lease out parts of the forest to the Timber Mafia.

Most of the teak trees in the forests of Siruseri were planted during the colonial times, after the native trees had been cut. Like everything European, the forest is very regular and orderly. It is rectangular in shape and the trees are arranged in uniformly spaced rows and coloumns.

Since the trees differ in height and girth, the timber value differs from tree to tree. The forest department has collected data on each tree and knows the volume of wood (in cubic feet) available in each tree in the forest.

The forest department maintains this information in the form of an M × N array of integers, where the (i,j)th entry is the volume, in cubic feet, of the jth tree on the ith row (or, equivalently, the ith tree on the jth column). We assume that our rows are numbered top to bottom and the columns are numbered from left to right. For example, such an array could look like

3	4	15	23
14	20	12	9
3	8	12	15
12	20	7	5

This array tells us that the volume of the tree at position (3,4) is 15 cubic feet and so on.

Any rectangular piece of land with trees at each corner can be leased out. In order to fix the lease price for any rectangular plot of the forest the forest department needs to know the amount of wood available inside the plot.

A rectangular plot is described by the positions of the trees in its top left corner and the bottom right corner. For example the positions (2,2) and (3,4) describes the following part rectangular part of the above forest.

20	12	9
8	12	15

The total amount of wood available in this rectangular plot is 76 cubic feet. Similarly (4,2) and (4,2) describes the rectangle with just one tree and its volume is 20 cubic feet.

Your task is to write a program that helps the forest department to compute the total volume of the trees insides any specfied rectangular plot.

Input format

The first line of the input contains two integers M and N indicating the number of rows and columns of trees in the forest. The following M lines have N integers each. The jth integer on line i+1 denotes the volume (in cubic feet) of the jth tree on the ith row. Line M+2 contains a single integer C indicating the number of rectangles for which the total volume is to be computed. Each of the following C lines (line M+2+1 ... M+2+C) each contain four integers x₁, y₁, x₂ and y₂ (with x₁ ≤ x₂ and y₁ ≤ y₂) and describes a rectangle. The rectangle has its top left corner at the tree in position (x₁,y₁) and its bottom right corner at the tree at position (x₂,y₂).

Output format

Your output must contain C lines with one integer on each line. Line i must contain the total volume of wood in the rectangle described on line M+2+i in the input.

Test Data:

You may assume 2 ≤ M ≤ 1000 and 2 ≤ N ≤ 1000. You may also assume that C ≤ 1000000. Further in 30% of the inputs C ≤ 100.

Example:

Here are the inputs and outputs corresponding to the example discussed above.

Sample 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

Sample Output

76
20