Kamome 對觀測流星非常感興趣。佢創建咗一個無限大嘅二維模型嚟模擬流星嘅運動（雖然呢個模型實際上並冇模擬任何嘢）。喺呢個模擬入面有 $n$ 個流星模型，第 $i$ 個流星模型嘅重量係 $m_i$。每個流星模型都沿住一條固定嘅直線以恆定嘅速度運動（亦可能係靜止嘅）。

自從 Kamome 開始運行呢個模型以嚟已經過咗好耐。有一日，Kamome 突然忽發奇想，對當前嘅模型影咗兩張相。以 Kamome 嘅位置作為原點，對於每張相 $i$（$i = 1, 2$），第 $j$ 個流星模型喺平面上面嘅位置係 $(x_{i,j}, y_{i,j})$。

你可以計算出每個流星模型嘅軌跡，但係咁樣仲未夠！Kamome 希望你計算出，對於每個流星模型 $i$，喺模型運行嘅成個過程入面（你可以認為影相之前同之後嘅時間都係無限長嘅），任何其他流星模型對佢產生嘅最大萬有引力。

注意，通常嘅萬有引力公式可以改寫為 $F = G \frac{m_1 m_2}{r^2} = \frac{G}{\frac{1}{m_1} \frac{1}{m_2} r^2}$。為咗避免處理一啲極端情況，Kamome 改為將 $m'_i = \frac{1}{m_i}$ 作為輸入畀你，而你只需要輸出將答案除以 $G$ 之後再取倒數嘅結果。即係話，對於每個 $i$，計算 $\min_{j \ne i} \min_{t \in \mathbb{R}} m'_i m'_j D_t^2(i, j)$，其中 $D_t(i, j)$ 係喺時刻 $t$ 流星模型 $i$ 同 $j$ 之間嘅距離，而 $t$ 可以係任意實數（負數、正數或者零）。

輸入格式

每個測試包含多組測試數據。第一行包含一個整數 $t$（$1 \le t \le 10^4$），表示測試數據嘅組數。接落嚟係測試數據嘅描述。

第一行包含一個整數 $n$（$2 \le n, \sum n \le 10^5$），表示流星模型嘅數量。

第二行包含 $n$ 個整數 $m'_i$（$1 \le m'_i \le 100$），佢嘅定義如上所述。

接落嚟嘅 $n$ 行，每行包含四個整數 $x_{1,i}, y_{1,i}, x_{2,i}, y_{2,i}$（$-10^8 \le 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$），表示第 $i$ 個流星模型喺兩張相入面嘅位置。

輸出格式

對於每組測試數據，輸出一行 $n$ 個實數，定義如上所述。

假設你嘅答案係 $x$，而評測嘅標準答案係 $y$，當且僅當 $\frac{|x - y|}{\max(y, 1)} \le 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 同流星模型 2 之間嘅最大引力發生喺佢哋分別到達 $(0.5, 0)$ 同 $(0.5, 1)$ 嘅時候。喺呢個時刻，答案係 $m'_1 m'_2 d_{\min}^2 = 2$。