택지

바이타자르는 어릴 적부터 바이토츠카 숲에 자기 택지를 갖는 것이 꿈이었고, 지금은 정보과학자로 일하며 마침내 그 꿈을 이룰 수 있게 되었다.

숲의 새로운 구역이 막 매물로 나왔고, 바이타자르는 그 첫 번째 손님이다. 위에서 내려다보면 이 구역은 한 변의 길이가 $k$인 $k \times k$ 정사각형이며, 그 안에는 소나무 $n$그루가 자라고 있다. 첫 번째 손님인 바이타자르는 여러 택지 후보 위치 중에서 하나를 고를 수 있다. 각 후보는 숲 안에 완전히 포함되는 직사각형이다. 그는 아직 어느 것을 살지 정하지 못했다.

택지를 사고 나면 바이타자르는 울타리를 칠 계획이다. 그는 알뜰해서, 택지 안에 자라는 모든 소나무를 감싸면서도 울타리 길이는 최대한 짧기를 바란다. 특히 이는 직사각형 택지 전체를 두를 필요는 없다는 뜻이다. 어떤 나무들의 집합을 감싸는 가장 짧은 울타리는 그 나무들의 볼록 껍질(convex hull)을 따라간다. 또한 그는 매년 울타리로 둘러싸인 영역의 넓이에 비례하는 토지세를 내야 하며, 그를 가장 걱정시키는 것이 바로 이 적지 않은 세금이다.

바이타자르를 도와, 제안된 각 택지 위치마다 울타리로 둘러싸인 영역의 넓이, 즉 택지 안에 있는 소나무들의 볼록 껍질의 넓이를 구하라.

첫째 줄에 두 정수 $k$와 $n$이 주어진다 ($1 \le k \le 1\,000\,000$, $3 \le n \le 3\,000$). 각각 숲 구역 한 변의 길이와 그 안에 자라는 소나무의 수이다. 이어지는 $n$개의 줄에는 각각 두 정수 $x_i$, $y_i$ ($0 \le x_i, y_i \le k$)가 주어지며, $i$번째 소나무의 좌표를 나타낸다. 한 점에는 소나무가 많아야 한 그루 있다고 가정해도 된다.

그다음 줄에는 정수 $m$ ($1 \le m \le 1\,000\,000$), 즉 가능한 택지 위치의 개수가 주어진다. 이어지는 $m$개의 줄에는 각각 네 정수 $a_j$, $b_j$, $c_j$, $d_j$ ($0 \le a_j < b_j \le k$, $0 \le c_j < d_j \le k$)가 주어지며, 직사각형 택지 $[a_j, b_j] \times [c_j, d_j]$를 나타낸다. 소나무는 $a_j \le x_i \le b_j$이고 $c_j \le y_i \le d_j$일 때 그 택지 안에 있는 것으로 센다(경계 포함).

$m$개의 줄을 출력한다. $j$번째 줄에는 $j$번째 택지 후보를 골랐을 때 울타리로 둘러싸인 영역의 넓이를 소수점 아래 한 자리까지 하나의 실수로 출력한다. 이 넓이는 항상 양수라고 가정해도 된다.

모든 소나무의 좌표가 정수이므로 볼록 껍질의 넓이는 항상 $0.5$의 배수이며, 따라서 소수점 아래 한 자리는 언제나 .0 또는 .5이다.

그림은 예제의 첫 두 택지 후보와, 그때 울타리로 둘러싸인 영역을 나타낸다.