Bajtazar has dreamed of owning a plot of land in the Byteotian Forest since he was a child. He now works as a computer scientist and can finally afford to make this dream a reality.

The Byteotian Forests company has just started selling plots in a new section of the forest, and Bajtazar was the first customer to apply. From a bird's-eye view, this section of the forest looks like a square of size $k \times k$ and contains $n$ pine trees. As the first customer, Bajtazar has many plot location offers to choose from. Each offer is a rectangle located entirely within this section of the forest. Bajtazar does not yet know which offer to choose.

After purchasing a plot, Bajtazar intends to enclose it with a fence. Bajtazar is frugal and would like the fence to be as short as possible while still enclosing all the trees growing within the plot area. This, in particular, means that the entire area of the rectangular plot does not necessarily have to be fenced. Bajtazar also knows that every year he will have to pay land tax, the amount of which will be proportional to the area of the fenced region of the plot. It is mainly this significant tax that worries Bajtazar.

Help Bajtazar make a decision and calculate, for each plot location proposed by Byteotian Forests, the area of the fenced region of the plot.

Input

The first line of input contains two integers $k$ and $n$ ($1 \le k \le 1\,000\,000$, $3 \le n \le 3\,000$), representing the side length of the forest section and the number of pine trees growing in this section. Each of the next $n$ lines contains two integers $x_{i}, y_{i}$ ($0 \le x_{i}, y_{i} \le k$), representing the coordinates of the $i$-th pine tree. You may assume that there is at most one pine tree at any given point.

The next line of input contains one integer $m$ ($1 \le m \le 1\,000\,000$), representing 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} \le 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}]$.

Output

Your program should output $m$ lines; the $j$-th line should contain a single real number, given with a precision of one decimal place, representing the area of the fenced region of the plot for the $j$-th offer. You may assume that this area will always be positive.

Examples

Input 1

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

Output 1

4.0
10.0
6.0

Note 1

The figure shows the first two plot location offers with the fenced area highlighted.