Bajtazar 从小就梦想着在巴伊特森林（Puszcza Bajtocka）中拥有一块土地。如今他是一名程序员，终于能够实现这个梦想。

巴伊特森林公司（Lasy Bajtockie）刚刚开始在这片森林的新区域出售土地，而 Bajtazar 是第一个报名的客户。该片森林从空中俯瞰呈一个边长为 $k \times k$ 的正方形，其中生长着 $n$ 棵松树。作为第一位客户，Bajtazar 有很多土地位置的选择机会。每一个选择对应于一个完全位于该片森林内的矩形地块。Bajtazar 现在还不知道该选择哪一个。

购地之后，Bajtazar 打算用篱笆将其围起来。他很节俭，希望篱笆尽可能短，同时能够围住地块上的所有树木。特别地，这意味着整个矩形地块不一定都要被围住。Bajtazar 也知道自己每年都必须缴纳与围起区域面积成正比的土地税。而正是这笔不小的税款令他十分担忧。

请帮助 Bajtazar 做出决定，计算出由巴伊特森林公司提供的每一个地块位置中，围住该地块上所有树木所需的围栏面积。

输入格式

输入的第一行包含两个整数 $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} \le b_{j} \le k$, $0 \le c_{j} < d_{j} \le k$），表示一个矩形地块 $[ a_{j}, b_{j} ] \times [ c_{j}, d_{j} ]$。

输出格式

你的程序应输出 $m$ 行；第 $j$ 行应包含一个实数，保留一位小数：表示选择第 $j$ 个方案时，围起地块上所有树木所需的最小面积。你可以假设该面积总是正数。

示例

输入

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

注释

图中展示了前两个地块选项以及围栏区域的示意图。