The Cake is a Dessert

View as PDF

Submit solution

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 (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
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 \text{cm}^3):

111100
111100
122100
011000
111111

To answer the queries, just look at the diagram above and add up the numbers in each rectangle.


Comments

There are no comments at the moment.