Kamome interessiert sich sehr für die Beobachtung von Meteoren. Er hat ein unendlich großes zweidimensionales Modell erstellt, das die Bewegung von Meteoren simuliert (auch wenn es eigentlich gar nichts simuliert). In dieser Simulation gibt es $n$ Meteormodelle, und das Gewicht des $i$-ten Meteormodells beträgt $m_i$. Jedes Meteormodell bewegt sich mit konstanter Geschwindigkeit entlang einer festen Geraden (es kann auch stillstehen).

Es ist schon lange her, seit Kamome dieses Modell gestartet hat. Eines Tages hatte Kamome plötzlich eine Idee und machte zwei Fotos des aktuellen Modells. Nimmt man Kamomes Position als Ursprung, so befand sich für jedes Foto $i$ ($i = 1, 2$) das $j$-te Meteormodell an der Position $(x_{i,j}, y_{i,j})$ in der Ebene.

Du kannst zwar die Flugbahn jedes Meteormodells berechnen, aber das reicht noch nicht! Kamome möchte, dass du für jedes Meteormodell $i$ die maximale Gravitationskraft berechnest, die irgendein anderes Meteormodell während der gesamten Laufzeit des Modells auf es ausübt (du kannst dir dies als eine unendliche Zeitspanne vor und nach der Aufnahme der Fotos vorstellen).

Beachte, dass die übliche Gravitationsformel als $F = G \frac{m_1 m_2}{r^2} = \frac{G}{\frac{1}{m_1} \frac{1}{m_2} r^2}$ umgeschrieben werden kann. Um einige Randfälle zu vermeiden, gibt dir Kamome stattdessen $m'_i = \frac{1}{m_i}$ als Eingabe, und du musst lediglich das Ergebnis ausgeben, das man erhält, wenn man die Antwort durch $G$ teilt und anschließend den Kehrwert bildet. Das heißt, berechne für jedes $i$ den Wert $\min_{j \ne i} \min_{t \in \mathbb{R}} m'_i m'_j D_t^2(i, j)$, wobei $D_t(i, j)$ der Abstand zwischen den Meteormodellen $i$ und $j$ zum Zeitpunkt $t$ ist und $t$ eine beliebige reelle Zahl (negativ, positiv oder null) sein kann.

Eingabe

Jeder Test enthält mehrere Testfälle. Die erste Zeile enthält eine ganze Zahl $t$ ($1 \le t \le 10^4$), die die Anzahl der Testfälle angibt. Es folgt die Beschreibung der Testfälle.

Die erste Zeile enthält eine ganze Zahl $n$ ($2 \le n, \sum n \le 10^5$), die die Anzahl der Meteormodelle angibt.

Die zweite Zeile enthält $n$ ganze Zahlen $m'_i$ ($1 \le m'_i \le 100$), deren Definition oben angegeben ist.

Die nächsten $n$ Zeilen enthalten jeweils vier ganze Zahlen $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$), die die Position des $i$-ten Meteormodells auf den beiden Fotos angeben.

Ausgabe

Gib für jeden Testfall eine Zeile mit $n$ reellen Zahlen aus, wie oben definiert.

Angenommen, deine Antwort lautet $x$ und die Antwort der Jury lautet $y$, dann gilt deine Antwort genau dann als korrekt, wenn $\frac{|x - y|}{\max(y, 1)} \le 10^{-6}$ erfüllt ist.

Beispiele

Eingabe 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

Ausgabe 1

2.000000000 2.000000000
3.000000000 4.000000000 3.000000000

Hinweis

Im ersten Testfall tritt die maximale Gravitationskraft zwischen Meteormodell 1 und Meteormodell 2 auf, wenn sie $(0.5, 0)$ bzw. $(0.5, 1)$ erreichen. Zu diesem Zeitpunkt lautet die Antwort $m'_1 m'_2 d_{\min}^2 = 2$.