题目描述

给定 $k\times k$ 平面中的 $n$ 个点，$m$ 次询问，每次询问一个边平行于坐标轴的矩形内部（包含边界）的点构成的凸包面积。

输入格式

第一行两个正整数 $k,n$。

接下来 $n$ 行，第 $i$ 行包含两个整数 $x_i,y_i$ 表示第 $i$ 个点的坐标。

之后一行一个数 $m$。

之后 $m$ 行，第 $i$ 行包含四个数 $a_i,b_i,c_i,d_i)$，表示询问左下角为 $(a_i,c_i)$，右上角为 $(b_i,d_i)$ 的矩形。

输出格式

对于每个询问输出一行表示面积。保留小数点后一位。

9 7
1 1
1 3
3 3
3 1
6 5
6 6
7 3
3
0 4 0 4
2 7 0 7
3 7 3 6

4.0
10.0
6.0

提示

$1\leq k\leq 10^6$，$3\leq n\leq 3\times 10^3$，$1\leq m\leq 10^6$，$0\leq x_i,y_i,a_i,b_i,c_i,d_i\leq k，a_i<c_i,b_i<d_i$。