Kamome hefur mikinn áhuga á að skoða loftsteina. Hann bjó til óendanlega stórt tvívítt líkan sem hermir eftir hreyfingu loftsteina (þótt það hermi í rauninni ekki eftir neinu). Það eru $n$ loftsteinalíkön í þessari hermun og þyngd $i$-ta loftsteinalíkansins er $m_i$. Hvert loftsteinalíkan hreyfist á jöfnum hraða eftir fastri beinni línu (það gæti líka verið kyrrstætt).

Langur tími er liðinn síðan Kamome setti þetta líkan í gang. Dag einn fékk Kamome skyndilega hugmynd og tók tvær ljósmyndir af núverandi líkani. Ef staðsetning Kamome er tekin sem upphafspunktur, þá var $j$-ta loftsteinalíkanið á hverri ljósmynd $i$ ($i = 1, 2$) staðsett í punktinum $(x_{i,j}, y_{i,j})$ á sléttunni.

Þú getur reiknað út feril hvers loftsteinalíkans, en það er ekki nóg! Kamome vill að þú reiknir út, fyrir hvert loftsteinalíkan $i$, hámarks þyngdarkraft sem nokkurt annað loftsteinalíkan verkar á það allan þann tíma sem líkanið hefur verið í gangi (þú getur litið á þetta sem óendanlegan tíma bæði fyrir og eftir að myndirnar voru teknar).

Athugaðu að hægt er að endurskrifa venjulegu þyngdarformúluna sem $F = G \frac{m_1 m_2}{r^2} = \frac{G}{\frac{1}{m_1} \frac{1}{m_2} r^2}$. Til að komast hjá því að glíma við jaðartilvik gefur Kamome þér í staðinn $m'_i = \frac{1}{m_i}$ sem inntak, og þú þarft aðeins að prenta út niðurstöðuna af því að deila svarinu með $G$ og taka svo umhverfuna. Það er, fyrir hvert $i$, reiknaðu $\min_{j \ne i} \min_{t \in \mathbb{R}} m'_i m'_j D_t^2(i, j)$, þar sem $D_t(i, j)$ er fjarlægðin milli loftsteinalíkana $i$ og $j$ á tíma $t$, og $t$ getur verið hvaða rauntala sem er (neikvæð, jákvæð eða núll).

Inntak

Hvert próf inniheldur mörg prófunartilvik. Fyrsta línan inniheldur eina heiltölu $t$ ($1 \le t \le 10^4$), sem gefur til kynna fjölda prófunartilvika. Lýsing á prófunartilvikunum fylgir á eftir.

Fyrsta línan inniheldur eina heiltölu $n$ ($2 \le n, \sum n \le 10^5$), sem gefur til kynna fjölda loftsteinalíkana.

Önnur línan inniheldur $n$ heiltölur $m'_i$ ($1 \le m'_i \le 100$), en skilgreining þeirra er eins og lýst er hér að ofan.

Næstu $n$ línur innihalda hver um sig fjórar heiltölur $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$), sem gefa til kynna staðsetningu $i$-ta loftsteinalíkansins á ljósmyndunum tveimur.

Úttak

Fyrir hvert prófunartilvik skal prenta út eina línu með $n$ rauntölum, eins og skilgreint er hér að ofan.

Gerum ráð fyrir að svarið þitt sé $x$ og svar dómnefndar sé $y$; svarið þitt telst rétt ef og aðeins ef $\frac{|x - y|}{\max(y, 1)} \le 10^{-6}$.

Dæmi

Inntak 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

Úttak 1

2.000000000 2.000000000
3.000000000 4.000000000 3.000000000

Skýring

Fyrir fyrsta prófunartilvikið verður hámarks þyngdarkraftur milli loftsteinalíkans 1 og loftsteinalíkans 2 þegar þau ná $(0.5, 0)$ og $(0.5, 1)$ hvoru um sig. Á þeim tímapunkti er svarið $m'_1 m'_2 d_{\min}^2 = 2$.