레이팅 미적용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.
The first line contains an integer N (\(1 \le N \le 100\,000\)), the number of sheets.
Each of the following N lines contains four integers \(x_{1}\), \(y_{1}\), \(x_{2}\) and \(y_{2}\) (−\(1\,000\,000 \le x_{1} \le x_{2} \le 1\,000\,000\)),
(−\(1\,000\,000 \le y_{1} \le y_{2} \le 1\,000\,000\)). The coordinates (\(x_{1}\), \(y_{1}\)) and (\(x_{2}\), \(y_{2}\)) 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 \le M \le 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.
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.
3
-2 1 1 2
1 0 2 1
-3 -3 -2 0
2
1 25
154
5 1 8 4
-8 1 -5 4
-10 2 10 3
6 0 8 10
6
1 2 3 4 7 90
5
14
18
70
1001
1 1 1000000 1000000
3
100 10000 100000010000
100000000
1000000000000