在 ICPC 银河系中，存在一片充满小行星的区域，进入该区域是不安全的。银河系的地图由二维笛卡尔坐标系表示。该区域呈一个 $N$ 边凸多边形。每个顶点从 1 到 $N$ 编号；顶点 $i$ 位于 $(X_i, Y_i)$。在任何时刻，你都不应处于该多边形内部；不过，触碰多边形的边是安全的。

共有 $Q$ 个场景（编号从 1 到 $Q$）。在场景 $j$ 中，你希望从起点 $(A_j, B_j)$ 前往终点 $(C_j, D_j)$。你将乘坐一艘只能沿直线行驶的特殊飞船。首先，你设定飞船的行驶方向，然后飞船开始沿该方向行驶。在行驶过程中，你最多只能改变一次方向。改变方向意味着你停止飞船，设定一个新的方向，然后再次开始沿新方向行驶。

对于每个场景，确定在任何时刻都不进入该区域的情况下所需的最短行驶距离，如果无法到达终点，则报告无法到达。

输入格式

第一行包含一个整数 $N$ ($3 \le N \le 100\,000$)。

接下来的 $N$ 行，每行包含两个整数 $X_i, Y_i$ ($-10^9 \le X_i, Y_i \le 10^9$)。这些点按逆时针顺序构成一个凸多边形。不存在三点共线的情况。

接下来一行包含一个整数 $Q$ ($1 \le Q \le 100\,000$)。

接下来的 $Q$ 行，每行包含四个整数 $A_j, B_j, C_j, D_j$ ($-10^9 \le A_j, B_j, C_j, D_j \le 10^9$)。起点和终点均不在区域内部。不过，起点和终点可能位于区域的边上。

输入中的所有坐标均为整数。

输出格式

对于每个场景，输出一行答案。

如果可以在任何时刻都不进入区域的情况下到达终点，则输出所需的最短行驶距离。否则，输出 $-1$。

如果你的答案与标准答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。即，如果你的答案为 $a$，标准答案为 $b$，则当 $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$ 时，你的答案被接受。

样例

输入 1

5
0 2
2 0
4 4
2 4
5 6
1 6 3
2 5 0 0
3 5 3 -1
1 4 5 4
3 4 3 0

输出 1

2
5.6055512755
8.48528137422
4
-1

说明 1

该样例描绘在下图中。

在场景 1 和 4 中，你可以直接前往终点而无需改变方向。

在场景 2 中，你可以先前往 $(0, 2)$，然后改变方向前往终点。

在场景 3 中，你可以先前往 $(6, 2)$，然后改变方向前往终点。

在场景 5 中，可以证明无法到达终点。

输入 2

4
-10 -9
10 -9
10 9
-10 9
2
0 10 0 -10
-10 -10 -10 -10

输出 2

200.9975124224
0

输入 3

8
-20 -10
10 -20
25 -15
35 -5
30 10
15 20
-25 15
-30 5
6
-15 -15 -15 20
-30 -5 30 15
25 20 -5 -20
-5 25 20 -20
-30 10 30 -10
-30 -50 50 0

输出 3

59.0857761929
103.2455532034
94.7213595500
101.5640991922
164.8528137424
94.3398113206