### Croatian Olympiad in Informatics 2009

## Task PLAHTE

Mirko washed his sheets and is on his way to hang them to dry in front of his house. However, strong winds have pulled the clothesline out of the ground so Mirko temporarily laid out the sheets on the grass.

The grass field can be modeled by an infinite square grid, where every **unit square** is represented by a pair of coordinates. Sheets are rectangles in the grid with sides parallel to the coordinate axes. Sheets may overlap.

In an effort to put his clothesline back up, Mirko slammed a pole into the ground at coordinates (0, 0). An entirely unexpected turn of events followed. Oil sprung from the ground and the shock caused Mirko to faint. While Mirko lay unconscious, the oil is spreading, staining his sheets.

Time is measured from the moment the oil starts spreading - at time zero only square (0, 0) is covered in oil. The oil is spreading at a speed of **one square per second in all eight directions**, as shown in the figure below. When oil enters a square, it stains that square of fabric on all sheets covering the square.

*The grass field from the first example after zero, one and two seconds.*

Write a program that, given M points in time, calculates the **total area of stained fabric** on all sheets for each of the given time points.

### Input

The first line contains an integer N (1 ≤ N ≤ 100 000), the number of sheets.

Each of the following N lines contains four integers x1, y1, x2 and y2 (-1 000 000 ≤ x1 ≤ x2 ≤ 1 000 000), (-1 000 000 ≤ y1 ≤ y2 ≤ 1 000 000). The coordinates (x1, y1) and (x2, y2) represent diagonally opposite corners of a sheet (again, these coordinates are unit squares, not points on the plane). None of the sheets will cover the square (0, 0).

The next line contains an integer M (1 ≤ M ≤ 100 000), the number of points in time.

The next line contains M integers between 0 and 1 000 000, the time points. They will be given in strictly ascending order.

### Output

For each of the time points, output on a separate line the total area of stained fabric on all sheets, in the order the time points are given in the input.

### Examples

## Sample Input3 -2 1 1 2 1 0 2 1 -3 -3 -2 0 2 1 2 ## Sample Output5 15 |
## Sample Input4 5 1 8 4 -8 1 -5 4 -10 2 10 3 6 0 8 10 6 1 2 3 4 7 9 ## Sample Output0 5 14 18 70 100 |
## Sample Input1 1 1 1000000 1000000 3 100 10000 1000000 ## Sample Output10000 100000000 1000000000000 |

All Submissions

Best Solutions

**Point Value:** 40 (partial)

**Time Limit:** 1.00s

**Memory Limit:** 128M

**Added:** Apr 26, 2009

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