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 \times N$ array of integers, where the
$(i, j)$th entry is the volume, in cubic feet, of the
$i^{th}$ tree on the $i^{th}$ row (or, equivalently, the
$i^{th}$ tree on the $i^{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

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.

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:-----
- 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$) contain four integers $x_1, y_1, x_2$ and $y_2$ (with $x_1 \leq x_2$ and $y_1 \leq y_2$) and describes a rectangle. The rectangle has its top left corner at the tree in position $(x_1,y_1)$ and its bottom right corner at the tree at position $(x_2,y_2)$.

-----Output:-----
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.

-----Constraints-----
- In $30 \%$ of inputs, $1 \leq C \leq 100$.
- In all inputs, $2 \leq N, M \leq 1000$ and $1 \leq C \leq 1000000$
- $0 \leq$ volume of wood in each tree $\leq 1000$
- $1 \leq x_1 \leq x_2 \leq M$
- $1 \leq y_1 \leq y_2 \leq N$

-----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

见题面

见题面