At the end of a tasty meal, Capba just wants some tasty dessert. Today,
his cafeteria is serving a rectangular cake, with a coordinate system
carved on its delicious graham cracker crust base. The cake can be
thought of as a 2D grid of squares, with square at the
bottom-left, and
at the top-right
.
The cake also has
different icings on it,
numbered from
to
, which have been applied in a strange fashion.
Icing
covers all squares in the rectangle from
to
, inclusive,
with
cubic centimeter (
) of icing each. If icings
overlap, there will be squares with multiple layers of icing on them;
for example, some of the squares in the sample input below are covered
by
of icing.
Capba likes icing… but then, he also doesn't like too much icing. He
considers
choices, numbered from
to
,
regarding which part of the cake to eat. Choice
involves cutting out
and rapidly consuming the rectangle from
to
, inclusive.
To decide on the best choice, he first wants to know how much icing is present in each potential piece of cake.
Input Specification
Line :
,
,
.
Next lines:
,
,
,
.
Next line: .
Next lines:
,
,
,
.
Output Specification
lines. Line
should contain the amount of icing present on the
piece of cake described by choice
, in
.
Note: The answers may overflow -bit integers.
Sample Input
6 5 3
1 3 4 5
1 1 6 1
2 2 3 3
5
2 1 2 2
5 2 6 5
2 4 2 4
3 1 4 2
2 1 4 4
Sample Output
2
0
1
3
13
Explanation for Sample Output
The cake has the following amounts of icing on it (in ):
111100
111100
122100
011000
111111
To answer the queries, just look at the diagram above and add up the numbers in each rectangle.
Comments