有一天，你在野外生存。经过一段时间的探索，你确定了一个安全区域，它是一个以 $n$ 个顶点 $P_1, P_2, \dots, P_n$ 为顶点的凸包，顶点按逆时针顺序给出，且任意三点不共线。

现在你收到通知，将会有 $q$ 次空投补给。对于第 $i$ 次补给，其投送范围由一个圆 $C_i$ 描述，这意味着补给将以均匀概率落在圆 $C_i$ 内部的所有实数坐标点上。

你非常需要这些补给，因此你决定为每次补给预先确定一个起点，不同补给的起点可以不同。每个起点都必须位于安全区域内，且使得该点到对应补给落点的欧几里得距离的平方的期望值最小。

回顾一下，在二维平面上，两点 $(x_1, y_1)$ 和 $(x_2, y_2)$ 之间的欧几里得距离为 $\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$。如果一个点的两个坐标均为整数，则称该点为整点。

输入格式

第一行包含两个整数 $n, q$ ($3 \le n, q \le 5000$)，分别表示安全区域的顶点数和空投补给的次数。

接下来的 $n$ 行，每行包含两个整数 $x_i, y_i$，表示安全区域第 $i$ 个顶点的坐标。

保证顶点按逆时针顺序给出，且任意三点不共线。

接下来的 $q$ 行，每行包含 4 个整数 $x_{i,1}, y_{i,1}, x_{i,2}, y_{i,2}$，表示连接 $(x_{i,1}, y_{i,1})$ 和 $(x_{i,2}, y_{i,2})$ 的线段是圆 $C_i$ 的直径。

所有输入的坐标均为整数，范围在 $[-10^9, 10^9]$ 内。

输出格式

对于每次空投补给，输出一行一个实数，表示欧几里得距离平方的最小期望值。如果你的答案为 $a$，裁判的答案为 $b$，当满足 $\frac{|a-b|}{\max(1,|b|)} \le 10^{-4}$ 时，你的答案将被视为正确。

样例

样例输入 1

4 3
0 0
1 0
1 1
0 1
0 0 1 1
1 1 2 2
1 1 2 3

样例输出 1

0.2500000000
0.7500000000
1.8750000000