## 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 (`x _{i}`,

`y`) to (

_{i}`X`,

_{i}`Y`) (1 ≤

_{i}`x`,

_{i}`X`≤

_{i}`N`, 1 ≤

`y`,

_{i}`Y`≤

_{i}`M`), inclusive, with 1 cubic centimeter (1 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 cm

^{3}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
(`A _{i}`,

`B`) to (

_{i}`C`,

_{i}`D`) (1 ≤

_{i}`A`≤

_{i}`C`≤

_{i}`N`, 1 ≤

`B`≤

_{i}`D`≤

_{i}`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 Format

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 Format

`Q` lines. Line `i` should contain the amount of icing
present on the piece of cake described by choice `i`, in
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

### Explanation

*[a better diagram would be nice]*

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

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...