Oil Spill Contamination on Sheets

There are \(N\) rectangular sheets placed on the ground. All sheets are parallel to the coordinate axes and none of them covers the cell \((0,0)\).

At time 0, oil covers cell \((0,0)\), and every subsequent time unit the oil spreads in all eight directions (including diagonals). When the oil reaches a cell that a sheet covers, it contaminates that cell on all sheets that cover it (only the contaminated cells on each sheet are counted).

At time \(t\), the oil covers all grid cells \((x,y)\) satisfying \( \max(|x|,|y|) \le t\).

Given several query times, compute the total contaminated area (in unit grid cells) over all sheets at each query time.

inputFormat

The first line contains two integers \(N\) and \(Q\) denoting the number of sheets and the number of queries respectively.

Each of the next \(N\) lines contains four integers \(x_1, y_1, x_2, y_2\) that describe a sheet covering all grid cells \(\{(x,y) \mid x_1 \le x \le x_2,\; y_1 \le y \le y_2\}\). It is guaranteed that no sheet covers the cell \((0,0)\).

The following \(Q\) lines each contain one integer \(t\), representing a query time.

outputFormat

For each query, print one integer on a separate line representing the total contaminated area (number of unit grid cells) across all sheets at time \(t\).

sample

1 2
1 1 3 3
1
2

1
4