[Croatian2009]PLAHTE

时间限制:20s      空间限制:162MB

题目描述

在一个无限大小的网格上有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

提示

没有写明提示


题目来源

没有写明来源