The Cake is a Dessert

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 ≤ N, M ≤ 5000).

The cake also has K (0 ≤ K ≤ 200000) 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 (xi,yi) to (Xi,Yi) (1 ≤ xi, XiN, 1 ≤ yi, YiM), inclusive, with 1 cubic centimeter (1 cm3) 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 cm3 of icing.

Capba likes icing... but then, he also doesn't like too much icing. He considers Q (1 ≤ Q ≤ 200000) 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 (Ai,Bi) to (Ci,Di) (1 ≤ AiCiN, 1 ≤ BiDiM), inclusive.

To decide on the best choice, he first wants to know how much icing is present in each potential piece of cake.

Input Format

Line 1: N, M, K

Next K lines: xi, yi, Xi, Yi

Next line: Q

Next Q lines: Ai, Bi, Ci, Di

Output Format

Q lines. Line i should contain the amount of icing present on the piece of cake described by choice i, in cm3.

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

Explanation

[a better diagram would be nice]

The cake has the following amounts of icing on it (in cm3):

111100
111100
122100
011000
111111

Sample Output

2
0
1
3
13

Explanation

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

All Submissions
Best Solutions


Point Value: 12
Time Limit: 10.00s
Memory Limit: 1024M
Added: Feb 22, 2011
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

It's quiet in here...