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
*j*th tree on the *i*th row (or, equivalently, the
*i*th tree on the *j*th 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 *j*th integer on line *i*+1
denotes the volume (in cubic feet) of the *j*th tree on
the *i*th 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 _{1}*,

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

Copyright (c) IARCS 2003-2018; Last Updated: 27 Dec 2004