Kamome bardzo interesuje się obserwacją meteorów. Stworzył nieskończenie duży, dwuwymiarowy model symulujący ruch meteorów (choć w rzeczywistości niczego nie symuluje). W tej symulacji znajduje się $n$ modeli meteorów, a masa $i$-tego modelu meteora wynosi $m_i$. Każdy model meteora porusza się ze stałą prędkością po ustalonej linii prostej (może być również nieruchomy).

Kamome od dawna nie uruchamiał tego modelu. Pewnego dnia wpadł na pomysł i zrobił dwa zdjęcia obecnego modelu. Przyjmując położenie Kamome jako początek układu, dla każdego zdjęcia $i$ ($i=1, 2$) $j$-ty model meteora znajdował się w punkcie $(x_{i,j}, y_{i,j})$ na płaszczyźnie.

Można obliczyć trajektorię każdego modelu meteora, ale to nie wystarczy! Kamome chce, abyś dla każdego modelu meteora $i$ obliczył maksymalną siłę grawitacyjną, jaką wywiera na niego inny model meteora przez cały czas trwania symulacji (można to traktować jako nieskończoną ilość czasu przed i po wykonaniu zdjęć).

Zauważ, że zwykły wzór na siłę grawitacji można zapisać jako $F = G \frac{m_1 m_2}{D^2}$. Aby uniknąć rozpatrywania szczególnych przypadków, Kamome podaje na wejściu zamiast tego $\frac{m_1 m_2}{G}$, a ty masz wypisać wynik podzielenia odpowiedzi przez $G$, a następnie wzięcia odwrotności. To znaczy, dla każdego $i$ oblicz $\min_{j \neq i} \min_{t \in \mathbb{R}} \frac{1}{m_i m_j D_t^2(i, j)}$, gdzie $D_t(i, j)$ to odległość między modelami meteorów $i$ i $j$ w czasie $t$, a $t$ może być dowolną liczbą rzeczywistą (ujemną, dodatnią lub zero).

Obrazek 1: Hoshizora

Wejście

Każdy przypadek testowy zawiera wiele zestawów danych. Pierwszy wiersz zawiera liczbę całkowitą $t$ ($1 \le t \le 10^4$), oznaczającą liczbę zestawów danych. Poniżej opisany jest każdy zestaw.

Pierwszy wiersz każdego zestawu zawiera dwie liczby całkowite $n$ ($2 \le n$, $\sum n \le 10^5$), oznaczające liczbę modeli meteorów. Drugi wiersz zawiera $n$ liczb całkowitych $m$ ($1 \le m \le 100$), których znaczenie podano wcześniej. Kolejne $n$ wierszy zawiera po cztery liczby całkowite: $x_{1,i}, y_{1,i}, x_{2,i}, y_{2,i}$ ($-10^8 < 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$), oznaczające położenie $i$-tego modelu meteora na dwóch zdjęciach.

Wyjście

Dla każdego zestawu danych wypisz wiersz składający się z $n$ liczb rzeczywistych, zgodnie z definicją podaną powyżej. Załóżmy, że twoja odpowiedź to $x$, a odpowiedź jury to $y$. Twoja odpowiedź jest uznawana za poprawną wtedy i tylko wtedy, gdy $\frac{|x - y|}{\max(y, 1)} < 10^{-6}$.

Przykład

Wejście 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

Wyjście 1

2.000000000 2.000000000
3.000000000 4.000000000 3.000000000

Uwagi 1

Dla pierwszego zestawu danych maksymalna siła grawitacyjna między modelem meteora 1 a modelem meteora 2 występuje, gdy znajdują się one odpowiednio w punktach (0.5, 0) i (0.5, 1). Wtedy odpowiedź wynosi $\frac{m_1 m_2}{m_1 m_2 \min(D_t^2(1,2))} = \frac{1}{\min(D_t^2(1,2))} = 2$.

Obrazek 2: Dwa zestawy danych