[Croatian2009]PLAHTE

在一个无限大的方格网格上有 $N$ 个矩形。每个矩形由左下角坐标 $(x_1,y_1)$ 和右上角坐标 $(x_2,y_2)$ 确定，其中矩形覆盖其边界上的所有网格，并包含坐标满足 $x_1\le x\le x_2$、$y_1\le y\le y_2$ 的网格。

油从源点 $(0,0)$ 渗出。在时刻 $0$，油覆盖网格 $(0,0)$；此后每经过 $1$ 秒，油会向周围的 $8$ 个方向各延伸 $1$ 格。因此，在时刻 $t$，油覆盖所有满足 $\max(|x|,|y|)\le t$ 的网格 $(x,y)$。

给定 $M$ 个询问，求在相应时刻所有矩形被油覆盖的面积之和。同一个网格若被多个矩形覆盖，则需要在每个矩形中分别计算。保证没有矩形覆盖网格 $(0,0)$。

输入格式

第一行包含一个整数 $N$，表示矩形的数量。

接下来 $N$ 行，每行包含 $4$ 个整数 $x_1$、$y_1$、$x_2$、$y_2$，表示一个矩形。

下一行包含一个整数 $M$，表示询问的数量。

接下来包含 $M$ 个整数，每个整数表示一个询问时刻。整数之间可以用空格或换行分隔。

输出格式

输出 $M$ 行，每行一个整数，表示对应时刻所有矩形被油覆盖的面积之和。

样例输入

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

样例输出

5
15

数据范围

• $1\le N,M\le 100000$；
• $-1000000\le x_1\le x_2\le 1000000$；
• $-1000000\le y_1\le y_2\le 1000000$；
• 每个询问时刻不超过 $1000000$。

来源与许可

本题为 Croatian 2009 试题「PLAHTE」，题面与测试数据整理自 BZOJ 1182。