在《英雄联盟》中，爆裂球果（Blast Cone）是一种带有爆炸性果实的植物。它们的爆炸威力足以将人类击飞数米远。
Cryin 利用爆裂球果来加速他和队友的移动。
假设你的角色现在位于召唤师峡谷。为简化起见：
- 召唤师峡谷可以被视为一个无限的二维平面，你的角色是一个忽略半径的点；
- 所有的障碍物都是边平行于坐标轴的矩形，你不能进入障碍物的严格内部，这意味着边界是可以通行的；
- 要使用爆裂球果，你可以移动到它的位置，将其摧毁，然后控制自己跳跃到距离 $R$ 以内除障碍物内部以外的任何位置。你可以假设这个过程是瞬时的，即不消耗任何时间。
这里有 $n$ 个矩形障碍物和 $m$ 个爆裂球果。现在你从起点 $(x_s, y_s)$ 出发，想要到达终点 $(x_t, y_t)$。你的移动速度是每秒 1 个单位长度。你能计算出从起点到终点的最小时间消耗吗？
输入格式
第一行包含三个整数 $n, m, R$ ($0 \le n, m \le 40, 1 \le R \le 10^6$)，分别表示矩形障碍物的数量、爆裂球果的数量和跳跃半径。
接下来的 $n$ 行中，第 $i$ 行包含四个整数 $x_{i,1}^b, y_{i,1}^b, x_{i,2}^b, y_{i,2}^b$ ($-10^6 \le x_{i,1}^b, y_{i,1}^b, x_{i,2}^b, y_{i,2}^b \le 10^6, x_{i,1}^b < x_{i,2}^b, y_{i,1}^b < y_{i,2}^b$)，表示第 $i$ 个障碍物的左下角为 $(x_{i,1}^b, y_{i,1}^b)$，右上角为 $(x_{i,2}^b, y_{i,2}^b)$。
接下来的 $m$ 行中，第 $i$ 行包含两个整数 $x_i^c, y_i^c$ ($-10^6 \le x_i^c, y_i^c \le 10^6$)，表示第 $i$ 个爆裂球果位于 $(x_i^c, y_i^c)$。
最后一行包含四个整数 $x_s, y_s, x_t, y_t$ ($-10^6 \le x_s, y_s, x_t, y_t \le 10^6$)，表示起点 $s$ 和终点 $t$。
保证：
- 任意两个障碍物不共享任何点，包括边界线和角。
- 爆裂球果的位置、起点 $s$ 和终点 $t$ 两两不同，且都严格位于障碍物外部。
输出格式
输出一个十进制实数，表示从起点到终点的最小时间消耗。如果你的答案与标准答案的相对误差或绝对误差不超过 $10^{-6}$，则视为正确。
保证在给定条件下存在有效解。
若要输出保留若干位小数的定点数（例如 9 位），可以使用：
- C 语言风格输出：
printf("%.9lf\n", ans)或printf("%.9Lf\n", ans)； - C++：
cout << fixed << setprecision(9) << ans << endl;； - Python：
print("%.9f" % ans)。
样例
样例输入 1
1 2 2 0 2 7 4 -3 3 8 2 1 1 6 6
样例输出 1
9.543203767
说明
样例输入的示意图如下：
答案为 $\sqrt{7^2 + 1^2} + \sqrt{2^2 + 4^2} - 2 \approx 9.543203767$。