Plot of Land

Byteasar has dreamed of owning a plot of land in the Byteotian Forest since childhood, and now, working as a computer scientist, he can finally afford to make that dream come true.

A new part of the forest has just gone on sale, and Byteasar is the very first customer. Seen from above, this part of the forest is a square of size $k \times k$, and $n$ pine trees grow inside it. As the first customer, Byteasar may choose among many proposed plot locations. Each proposal is a rectangle that lies entirely inside the forest. He has not yet decided which one to take.

After buying a plot, Byteasar intends to fence it. He is thrifty and wants the fence to be as short as possible while still enclosing every pine that grows on the plot. In particular, this means he does not have to fence the whole rectangular plot: the shortest fence that surrounds a set of trees runs along their convex hull. He also knows that every year he must pay a land tax proportional to the area of the fenced region, and it is mainly this sizeable tax that worries him.

Help Byteasar decide: for each plot location proposed by the forestry company, compute the area of the fenced region, that is, the area of the convex hull of the pines that lie inside that plot.

The first line contains two integers $k$ and $n$ ($1 \le k \le 1\,000\,000$, $3 \le n \le 3\,000$): the side length of the forest fragment and the number of pines growing in it. Each of the next $n$ lines contains two integers $x_i$, $y_i$ ($0 \le x_i, y_i \le k$): the coordinates of the $i$-th pine. You may assume that at most one pine stands at any given point.

The next line contains one integer $m$ ($1 \le m \le 1\,000\,000$): the number of possible plot locations. Each of the next $m$ lines contains four integers $a_j$, $b_j$, $c_j$, $d_j$ ($0 \le a_j < b_j \le k$, $0 \le c_j < d_j \le k$), describing the rectangular plot $[a_j, b_j] \times [c_j, d_j]$. A pine counts as lying inside this plot when $a_j \le x_i \le b_j$ and $c_j \le y_i \le d_j$ (the plot boundary is included).

Print $m$ lines. The $j$-th line should contain a single real number, given to one digit after the decimal point: the area of the fenced region if the $j$-th offer is chosen. You may assume that this area is always positive.

Because every pine sits at integer coordinates, the hull area is always a multiple of $0.5$, so the single decimal digit is always either .0 or .5.

The figure shows the first two proposed plot locations from the sample, with the fenced region highlighted.