Kamome är mycket intresserad av att observera meteorer. Han skapade en oändligt stor tvådimensionell modell som simulerar meteorers rörelse (även om den egentligen inte simulerar någonting alls). Det finns $n$ meteormodeller i denna simulering, och vikten på den $i$-te meteormodellen är $m_i$. Varje meteormodell rör sig med konstant hastighet längs en fast rät linje (den kan också stå stilla).

Det har gått lång tid sedan Kamome startade denna modell. En dag fick Kamome en plötslig idé och tog två foton av den aktuella modellen. Med Kamomes position som origo befann sig den $j$-te meteormodellen för varje foto $i$ ($i = 1, 2$) på positionen $(x_{i,j}, y_{i,j})$ i planet.

Du kan beräkna banan för varje meteormodell, men det räcker inte! Kamome vill att du för varje meteormodell $i$ beräknar den maximala gravitationskraft som någon annan meteormodell utövar på den under hela den tid som modellen har körts (du kan betrakta detta som en oändlig tidsrymd både före och efter att fotona togs).

Observera att den vanliga gravitationsformeln kan skrivas om som $F = G \frac{m_1 m_2}{r^2} = \frac{G}{\frac{1}{m_1} \frac{1}{m_2} r^2}$. För att slippa hantera vissa extremfall ger Kamome dig istället $m'_i = \frac{1}{m_i}$ som indata, och du behöver bara skriva ut resultatet av att dividera svaret med $G$ och sedan ta inverterade värdet. Det vill säga, för varje $i$, beräkna $\min_{j \ne i} \min_{t \in \mathbb{R}} m'_i m'_j D_t^2(i, j)$, där $D_t(i, j)$ är avståndet mellan meteormodellerna $i$ och $j$ vid tidpunkten $t$, och $t$ kan vara vilket reellt tal som helst (negativt, positivt eller noll).

Indata

Varje test innehåller flera testfall. Den första raden innehåller ett heltal $t$ ($1 \le t \le 10^4$), som anger antalet testfall. Beskrivningen av testfallen följer.

Den första raden innehåller ett heltal $n$ ($2 \le n, \sum n \le 10^5$), som anger antalet meteormodeller.

Den andra raden innehåller $n$ heltal $m'_i$ ($1 \le m'_i \le 100$), vars definition anges ovan.

De följande $n$ raderna innehåller var och en fyra heltal $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$), som anger positionen för den $i$-te meteormodellen på de två fotona.

Utdata

För varje testfall, skriv ut en rad med $n$ reella tal, enligt definitionen ovan.

Antag att ditt svar är $x$ och juryns svar är $y$; ditt svar betraktas som korrekt om och endast om $\frac{|x - y|}{\max(y, 1)} \le 10^{-6}$.

Exempel

Indata 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

Utdata 1

2.000000000 2.000000000
3.000000000 4.000000000 3.000000000

Förklaring

För det första testfallet inträffar den maximala gravitationskraften mellan meteormodell 1 och meteormodell 2 när de når $(0.5, 0)$ respektive $(0.5, 1)$. Vid denna tidpunkt är svaret $m'_1 m'_2 d_{\min}^2 = 2$.