Alice 和 Bob 正在使用一辆玩具太阳能小车进行行李运送游戏。游戏场地中放置了若干根杆子。

游戏开始时，太阳能小车被放置在某根杆子旁边，并将相同或另一根杆子标记为目的地。Bob 选择一根杆子并将行李放在那里。然后，Alice 规划一条小车的路线，以便去取行李并将其送到标记的目的地。Alice 会选择最短的可能路线，而 Bob 应该选择一根杆子以最大化该路线的长度。

太阳能小车可以行驶任意路线，但由于它没有电池，一旦进入阴影区域就会停止。在这个游戏中，场地表面有一个点光源，因此杆子会在光源位置的相反方向投下无限长的阴影。行驶路线必须避开所有这些阴影。

当给定太阳能小车的初始位置和目的地时，假设双方都做出最优选择，行驶路线的长度是唯一确定的。

考虑所有可能的博弈配置，给定两组杆子，一组用于太阳能小车的起始位置，另一组用于目的地。当初始小车位置和目的地都从各自的集合中均匀随机选择时，预期的路线长度是多少？

你的任务是根据给定的初始小车位置集合和目的地集合，计算路线长度的期望值。

输入格式

输入包含单个测试用例，格式如下：

$n$ $x_1 \ y_1$ $\vdots$ $x_n \ y_n$ $p$ $a_1 \ b_1 \ c_1 \ d_1$ $\vdots$ $a_p \ b_p \ c_p \ d_p$

其中 $n$ 是杆子的数量 ($3 \le n \le 2000$)。杆子编号为 $1$ 到 $n$，第 $i$ 根杆子位于整数坐标 $(x_i, y_i)$ ($-1000 \le x_i \le 1000, -1000 \le y_i \le 1000$)。点光源位于 $(0, 0)$。杆子不会放置在 $(0, 0)$ 处，也不会位于另一根杆子的阴影中，且没有两根杆子位于相同坐标。

$p$ 是集合对的数量 ($1 \le p \le 10^5$)。第 $i$ 对集合由四个整数 $(a_i, b_i, c_i, d_i)$ 指定 ($1 \le a_i \le b_i \le n, 1 \le c_i \le d_i \le n$)。具体来说，太阳能小车初始放置在第 $j$ 根杆子处，其中 $j$ 从 $\{a_i, \dots, b_i\}$ 中均匀随机选择，目的地杆子也从 $\{c_i, \dots, d_i\}$ 中均匀随机选择。

输出格式

输出每对集合的答案。绝对误差或相对误差小于 $10^{-7}$ 均可。

样例

样例输入 1

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

样例输出 1

24.000000000000
20.440306508911
20.000000000000
19.000000000000
15.440306508911
21.606571644990

说明

对于该测试用例的第一对集合，太阳能小车放置在 $(7, 0)$，旗帜（目的地）放置在 $(0, 7)$。然后，Bob 将行李放在 $(-7, 0)$。从 $(-7, 0)$ 到 $(0, 7)$ 的最短路线长度为 $10$，因为从 $(-7, 0)$ 到 $(0, 7)$ 的直线路径穿过了第 $4$ 根杆子的阴影。从 $(7, 0)$ 到 $(-7, 0)$ 的最短路线长度为 $14$，因此总长度为 $24$。

图 F.1. 样例输入 1 中前五对集合的最短路线。黑点是杆子的位置，灰线是它们的阴影。黄褐色点是点光源的位置。对于每张图，红线表示从初始小车位置到目的地的最短路线。