Kamome er veldig interessert i å observere meteorer. Han lagde en uendelig stor todimensjonal modell som simulerer bevegelsen til meteorer (selv om den egentlig ikke simulerer noen ting). Det er $n$ meteormodeller i denne simuleringen, og vekten til den $i$-te meteormodellen er $m_i$. Hver meteormodell beveger seg med konstant fart langs en fast rett linje (den kan også stå i ro).

Det har gått lang tid siden Kamome startet denne modellen. En dag fikk Kamome plutselig en idé og tok to bilder av den nåværende modellen. Med Kamomes posisjon som origo befant den $j$-te meteormodellen seg for hvert bilde $i$ ($i = 1, 2$) i posisjonen $(x_{i,j}, y_{i,j})$ i planet.

Du kan beregne banen til hver meteormodell, men det er ikke nok! Kamome vil at du skal beregne, for hver meteormodell $i$, den maksimale gravitasjonskraften som en hvilken som helst annen meteormodell utøver på den i løpet av hele tiden modellen har kjørt (du kan betrakte dette som en uendelig mengde tid før og etter at bildene ble tatt).

Merk at den vanlige gravitasjonsformelen kan skrives om som $F = G \frac{m_1 m_2}{r^2} = \frac{G}{\frac{1}{m_1} \frac{1}{m_2} r^2}$. For å unngå å håndtere noen spesialtilfeller gir Kamome deg i stedet $m'_i = \frac{1}{m_i}$ som inndata, og du trenger bare å skrive ut resultatet av å dele svaret på $G$ og deretter ta den inverse verdien. Det vil si, for hver $i$, beregn $\min_{j \ne i} \min_{t \in \mathbb{R}} m'_i m'_j D_t^2(i, j)$, der $D_t(i, j)$ er avstanden mellom meteormodellene $i$ og $j$ ved tidspunktet $t$, og $t$ kan være et hvilket som helst reelt tall (negativt, positivt eller null).

Inndata

Hver test inneholder flere testtilfeller. Den første linjen inneholder ett heltall $t$ ($1 \le t \le 10^4$), som angir antall testtilfeller. Beskrivelsen av testtilfellene følger.

Den første linjen inneholder ett heltall $n$ ($2 \le n, \sum n \le 10^5$), som angir antallet meteormodeller.

Den andre linjen inneholder $n$ heltall $m'_i$ ($1 \le m'_i \le 100$), definert som angitt ovenfor.

De neste $n$ linjene inneholder hver fire heltall $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 angir posisjonen til den $i$-te meteormodellen på de to bildene.

Utdata

For hvert testtilfelle skal du skrive ut én linje med $n$ reelle tall, som definert ovenfor.

Anta at svaret ditt er $x$ og juryens svar er $y$; svaret ditt regnes som riktig hvis og bare hvis $\frac{|x - y|}{\max(y, 1)} \le 10^{-6}$.

Eksempler

Inndata 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

Forklaring

For det første testtilfellet oppstår den maksimale gravitasjonskraften mellom meteormodell 1 og meteormodell 2 når de når henholdsvis $(0.5, 0)$ og $(0.5, 1)$. På dette punktet er svaret $m'_1 m'_2 d_{\min}^2 = 2$.