Problem Description

Given $n$ points on a $k \times k$ plane and $m$ queries, for each query, find the area of the convex hull formed by the points inside (including the boundary) an axis-aligned rectangle.

Input Format

The first line contains two positive integers $k, n$.

The next $n$ lines each contain two integers $x_i, y_i$, representing the coordinates of the $i$-th point.

Then a line contains one integer $m$.

The next $m$ lines each contain four numbers $a_i, b_i, c_i, d_i$, representing a query rectangle with bottom-left corner $(a_i, c_i)$ and top-right corner $(b_i, d_i)$.

Output Format

For each query, output one line with the area. Keep one digit after the decimal point.

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

Hint

$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$.

Translated by ChatGPT 5