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$。