Codah ClubGyakorolj. Küldd be. Fejlődj.
Bejelentkezés
Magyar
#00024F

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.

Image: dsadsa

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.


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

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


Input
3
-2 1 1 2
1 0 2 1
-3 -3 -2 0
2
1 2
Output
5
15

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.