Kamomeは流星観測に非常に興味を持っています。彼は流星の動きをシミュレートする（実際には何もシミュレートしていませんが）無限に広い2次元モデルを作成しました。このシミュレーションには$n$個の流星モデルがあり、$i$番目の流星モデルの重さは$m_i$です。各流星モデルは、固定された直線に沿って一定速度で移動します（静止していることもあります）。

長い間、Kamomeはこのモデルを実行していませんでした。ある日、突然ひらめいて、現在のモデルの写真を2枚撮りました。Kamomeの位置を原点として、写真$i$（$i=1,2$）において、$j$番目の流星モデルは平面上の位置$(x_{i,j}, y_{i,j})$にありました。

各流星モデルの軌跡を計算することはできますが、それだけでは十分ではありません！Kamomeは、各流星モデル$i$について、モデル実行中の全期間（写真を撮る前後の無限の時間と考えることができます）において、他の流星モデルから受ける最大重力を計算してほしいと望んでいます。

通常の重力式は$F = G \frac{m_1 m_2}{D^2}$と書き直せます。いくつかの特殊なケースを避けるため、Kamomeは入力として代わりに$\frac{m_1 m_2}{G}$を与え、答えを$G$で割ってからその逆数を出力する必要があります。すなわち、各$i$について、$\min_{j \neq i} \min_{t \in \mathbb{R}} \frac{1}{m_i m_j D_t^2(i, j)}$を計算してください。ここで$D_t(i, j)$は時刻$t$における流星モデル$i$と$j$の距離であり、$t$は任意の実数（負、零、正）です。

図1: Hoshizora

入力

各テストケースは複数のテストケースを含みます。最初の行には整数$t$ ($1 \le t \le 10^4$) が含まれ、テストケースの数を示します。以下に各テストケースが続きます。

各テストケースの最初の行には2つの整数$n$ ($2 \le n, \sum n \le 10^5$) が含まれ、流星モデルの数を示します。 2行目には$n$個の整数$m$ ($1 \le m \le 100$) が含まれ、その定義は上記の通りです。 次の$n$行にはそれぞれ4つの整数$x_{1,i}, y_{1,i}, x_{2,i}, y_{2,i}$ ($-10^8 < x_{1,i}, y_{1,i}, x_{2,i}, y_{2,i} \le 10^8$, $0 \le |x_{1,i} - x_{2,i}|, |y_{1,i} - y_{2,i}| \le 5$) が含まれ、2枚の写真における$i$番目の流星モデルの位置を示します。

出力

各テストケースについて、上記で定義された$n$個の実数を1行に出力してください。 答えが$x$で、正解が$y$であるとき、$\frac{|x - y|}{\max(y, 1)} < 10^{-6}$ が成り立てば正解とみなされます。

入出力例

入力例 1

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

出力例 1

2.000000000 2.000000000
3.000000000 4.000000000 3.000000000

注記 1

最初のテストケースでは、流星モデル1と流星モデル2の最大重力は、それぞれが(0.5,0)と(0.5,1)に達したときに発生します。そのとき、答えは$\frac{m_1 m_2}{m_1 m_2 \min(D_t^2(1,2))} = \frac{1}{\min(D_t^2(1,2))} = 2$となります。

図2: 2つのテストケース