题目描述

在一个无限大小的网格上有 $n$ 个矩形，给定每个矩形的坐标 $x_1, y_1, x_2, y_2$。

在源点处有油渗出，时刻 $0$ 时覆盖 $(0,0)$ 格，之后每秒钟会向周围 $8$ 个方向各延伸 $1$ 格。给定 $m$ 个询问，回答相应时刻时所有矩形被覆盖的面积之和。

若同一格被不同矩形覆盖，则需要多次计算。没有矩形覆盖 $(0,0)$ 格。

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

5
15

数据规模与约定

对于 $100\%$ 的数据：

• $1\le n, m\le 1\times 10^5$；
• $-10^6\le x_1\le x_2\le 10^6$；
• $-10^6\le y1\le y2\le 10^6$；
• 询问的时刻不超过 $10^6$。