Clothesline

On a Sunday, Changyoung washed every bed sheet in the house and was drying them on the lawn in front of his home. Suddenly, a strong gust of wind blew all of the sheets down onto the ground.

The lawn can be modeled as an infinitely large square grid. Each unit square is represented by an integer coordinate pair (x, y). Each sheet is an axis-aligned rectangle, and sheets may overlap.

To hang the sheets back on the clothesline, Changyoung placed a pole at (0, 0). At that moment, oil began to come out of the ground. Shocked by this unexpected situation, Changyoung fainted, and while he was unconscious the oil kept spreading.

Time is measured from the moment the oil starts spreading. At time 0, only the unit square (0, 0) contains oil. Every second, the oil moves one square in each of the eight directions, as shown below. Once oil enters a unit square, that entire square is filled immediately, and any sheet covering that square is stained.

The figure shows times 0, 1, and 2. For each given time, compute the total area of bed sheets stained by oil after that much time has passed. If sheets overlap, an overlapping unit square contributes once for each sheet covering it.

The first line contains the number of bed sheets N, where 1 <= N <= 100000.

Each of the next N lines contains four integers x1 y1 x2 y2 describing one sheet. The constraints are -1000000 <= x1 <= x2 <= 1000000 and -1000000 <= y1 <= y2 <= 1000000. The coordinates (x1, y1) and (x2, y2) are the coordinates of two diagonal unit squares covered by the sheet; they are not points on the coordinate plane. No sheet contains the unit square (0, 0).

The next line contains the number of query times M, where 1 <= M <= 100000.

The following M integers are the query times. Each time is an integer between 0 and 1000000, inclusive. They are given in increasing order, with no duplicates.

For each query time, output the area of the bed-sheet region stained by oil after that time has passed, one answer per line.