問題文

ストーリー

hibit 君は、競技プログラマーの運動不足解消のため、斬新なルールのイベント「障害物競プロ」を開催することにしました。
障害物競プロはたくさんの丸太が設置されている森の中で開催されます。
各参加者は、各スタート地点から丸太と接触しないように自分のパソコンまで走っていき、競技プログラミングを始めます。

森の中に $N$ 本の丸太があり、$i\ (1\leq i\leq N)$ 本目の丸太は座標平面上の点 $(x_{i,1},y_{i,1})$ から点 $(x_{i,2},y_{i,2})$ までの線分として表されます。
ただし、全ての丸太の端点の座標は異なり、ある丸太上に別の丸太の端点は存在しないことが保証されます。
また、参加者は $M$ 人 おり、$j\ (1\leq j\leq M)$ 人目の参加者はある丸太の端点である座標 $(x_{a_j,b_j},y_{a_j,b_j})$ からスタートして、別の丸太の端点であり自分のパソコンが置いてある座標 $(x_{c_j,d_j},y_{c_j,d_j})$ まで、その移動経路が始点と終点を除いてどの丸太とも共有点を持たないように走ります。

参加者は全員競技プログラマーであるため、なるべく短い距離で自分のパソコンまで移動したいと考えています。
各参加者について移動経路として取りうるすべての経路の長さがある実数 $x$ よりも小さくできないことが言えます。
そのような実数 $x$ として考えられる最大のものを出力してください。（2023/08/15 問題文を修正しました。）

入力

$N\ M$
$x_{1,1}\ y_{1,1}\ x_{1,2}\ y_{1,2}$
$x_{2,1}\ y_{2,1}\ x_{2,2}\ y_{2,2}$
$\vdots$
$x_{N,1}\ y_{N,1}\ x_{N,2}\ y_{N,2}$
$a_1\ b_1\ c_1\ d_1$
$a_2\ b_2\ c_2\ d_2$
$\vdots$
$a_M\ b_M\ c_M\ d_M$

• $2\leq N\leq 150$
• $1\leq M\leq 2\times 10^5$
• $-10^4\leq x_{i,j}\leq 10^4\ (1\leq i\leq N, j\in \{1,2\})$
• $-10^4\leq y_{i,j}\leq 10^4\ (1\leq i\leq N, j\in \{1,2\})$
• $(x_{i,j},y_{i,j})\neq(x_{k,l},y_{k,l})\ (1\leq i< k\leq N, j\in \{1,2\}, l\in \{1,2\})$
• $(x_{i,1},y_{i,1})\neq(x_{i,2},y_{i,2})(1\leq i\leq N)$
• $a_i\neq c_i\ (1\leq i\leq M)$
• $1\leq a_i,c_i \leq N\ (1\leq i\leq M)$
• $b_i\in \{1,2\}\ (1\leq i\leq M)$
• $d_i\in \{1,2\}\ (1\leq i\leq M)$
• 入力は全て整数
• ある丸太上に別の丸太の端点は存在しないことが保証される
• 全ての参加者が自分のパソコンまで移動できることが保証される

出力

$M$ 行出力してください。$j\ (1\leq j \leq M)$ 行目には、$j$ 人目の参加者のスタート位置からその人のパソコンまでの距離を小数、もしくは整数で出力してください。
厳密な答えとの絶対誤差または相対誤差が $10^{-5}$ 以下の場合に正解と判定されます。

サンプル

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

2.828427124746190097603377448

3 2
-1 1 2 0
0 0 2 2
0 2 3 0
1 1 2 2
3 1 1 2

3.414213562373095048801688724
4.828427124746190097603377448

5 5
8808 -2051 -3691 1776
-9697 -4260 -4971 -5119
6418 873 -7379 1473
9760 -4164 -6052 -7422
-2542 107 7881 -6992
4 1 1 2
3 1 5 1
3 2 5 2
5 2 3 1
3 2 1 2

16243.29816644555816987499627
15329.82119913967391662529792
21443.82128111283344796709709
9489.371445617676854468967106
3700.426056550785882761689606

3 1
1 2 9 8
5 2 1 0
1 4 1 7
1 1 2 2

2