5182: BZOJ1182：[Croatian2009]PLAHTE

在一个无限大小的网格上有N个矩形，给定每个矩形的坐标x1,y1,x2,y2。在源点处有油渗出，时刻0时覆盖(0,0)格，之后每秒钟会向周围8个方向各延伸1格。给定M个询问，回答相应时刻时所有矩形被覆盖的面积之和。若同一格被不同矩形覆盖，则需要多次计算。没有矩形覆盖(0,0)格。1<= N,M≤100000。 -1000000≤x1≤x2≤1000000，-1000000≤y1≤y2≤1000000。询问的时刻不超过1000000。

输入格式

输出格式

样例输入

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

样例输出

5
15

提示

没有写明提示

题目来源

没有写明来源