P8363 [COI 2009] PLAHTE

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.

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 $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).

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