## The Cake is a Dessert

View as PDF

Points: 10
Time limit: 4.5s
Memory limit: 1G

Author:
Problem type

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.