Problem Description

There are $N$ rectangular sheets on the plane. All sheets are parallel to the coordinate axes, and none of the sheets covers the cell $(0,0)$.

At time $0$, oil covers the cell $(0,0)$. At each subsequent time step, the oil spreads to the eight neighboring directions. When the oil spreads onto a cell that contains sheets, the oil contaminates all sheets on that cell (only the contaminated cells are counted; other unaffected parts are not).

Given several time moments, for each moment you need to find the total contaminated area (in cells) over all sheets.

Input Format

The first line contains a positive integer $N$, the number of sheets.

The next $N$ lines each contain four positive integers $x_1, y_1, x_2, y_2$. The $i$-th sheet is the rectangle formed by the two coordinates $(x_1, y_1)$ and $(x_2, y_2)$.

The next line contains a positive integer $M$, the number of time moments.

The next line contains $M$ positive integers, the time moments.

Output Format

Output $M$ lines. The $i$-th line should be the contaminated area of sheets at the $i$-th time moment (if two sheets overlap, the overlapped area is counted twice).

3
-2 1 1 2
1 0 2 1
-3 -3 -2 0
2
1 2 

5
15

4
5 1 8 4
-8 1 -5 4
-10 2 10 3
6 0 8 10
6
1 2 3 4 7 9

0
5
14
18
70
100

1
1 1 1000000 1000000
3
100 10000 1000000

10000
100000000
1000000000000

Hint

Constraints:

$1 \le N, M \le 10^5$.

$-10^6 \le x_1 \le x_2 \le 10^6$, $-10^6 \le y_1 \le y_2 \le 10^6$.

Translated by ChatGPT 5