The Cake is a Dessert

View as PDF

Submit solution

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

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 (1,1) at the bottom-left, and (N,M) at the top-right (1 \le N, M \le 5\,000).

The cake also has K (0 \le K \le 200\,000) different icings on it, numbered from 1 to K, which have been applied in a strange fashion. Icing i covers all squares in the rectangle from (x_{i},y_{i}) to (X_{i},Y_{i}) (1 \le x_{i}, X_{i} \le N, 1 \le y_{i}, Y_{i} \le M), inclusive, with 1 cubic centimeter (1 \text{cm}^3) 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 2 \text{cm}^3 of icing.

Capba likes icing... but then, he also doesn't like too much icing. He considers Q (1 \le Q \le 200\,000) choices, numbered from 1 to Q, regarding which part of the cake to eat. Choice i involves cutting out and rapidly consuming the rectangle from (A_{i},B_{i}) to (C_{i},D_{i}) (1 \le A_{i} \le C_{i} \le N, 1 \le B_{i} \le D_{i} \le
M), 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 1: N, M, K.
Next K lines: x_{i}, y_{i}, X_{i}, Y_{i}.
Next line: Q.
Next Q lines: A_{i}, B_{i}, C_{i}, D_{i}.

Output Specification

Q lines. Line i should contain the amount of icing present on the piece of cake described by choice i, in \text{cm}^3.

Note: The answers may overflow 32-bit integers.

Sample Input

6 5 3
1 3 4 5
1 1 6 1
2 2 3 3
2 1 2 2
5 2 6 5
2 4 2 4
3 1 4 2
2 1 4 4


The cake has the following amounts of icing on it (in \text{cm}^3):


Sample Output



Just look at the diagram above and add up the numbers in each rectangle.


There are no comments at the moment.