Énoncé

Kamome s'intéresse beaucoup à l'observation des météores. Il a créé un modèle bidimensionnel infiniment grand qui simule le mouvement des météores (même s'il ne simule rien en réalité). Il y a $n$ modèles de météores dans cette simulation, et le poids du $i$-ème modèle de météore est $m_i$. Chaque modèle de météore se déplace à une vitesse constante le long d'une ligne droite fixe (il peut aussi être stationnaire).

Cela fait longtemps que Kamome n'a pas exécuté ce modèle. Un jour, Kamome a eu une idée soudaine et a pris deux photos du modèle actuel. En prenant la position de Kamome comme origine, pour chaque photo $i$ ($i=1, 2$), le $j$-ème modèle de météore était situé à la position $(x_{i,j}, y_{i,j})$ dans le plan.

Vous pouvez calculer la trajectoire de chaque modèle de météore, mais ce n'est pas suffisant ! Kamome veut que vous calculiez, pour chaque modèle de météore $i$, la force gravitationnelle maximale qu'un autre modèle de météore lui exerce pendant toute la durée de l'exécution du modèle (vous pouvez considérer cela comme une quantité infinie de temps avant et après la prise des photos).

Notez que la formule gravitationnelle habituelle peut être réécrite comme $F = G \frac{m_1 m_2}{D^2}$. Pour éviter de traiter certains cas particuliers, Kamome vous donne plutôt $\frac{m_1 m_2}{G}$ comme entrée, et vous devez seulement sortir le résultat de la division de la réponse par $G$ puis en prenant l'inverse. C'est-à-dire, pour chaque $i$, calculez $\min_{j \neq i} \min_{t \in \mathbb{R}} \frac{1}{m_i m_j D_t^2(i, j)}$, où $D_t(i, j)$ est la distance entre les modèles de météores $i$ et $j$ au temps $t$, et $t$ peut être n'importe quel nombre réel (négatif, positif ou zéro).

Picture 1: Hoshizora

Entrée

Chaque cas de test contient plusieurs cas de test. La première ligne contient un entier $t$ ($1 \le t \le 10^4$), indiquant le nombre de cas de test. La description des cas de test suit.

La première ligne contient deux entiers $n$ ($2 \le n, \sum n \le 10^5$), indiquant le nombre de modèles de météores. La deuxième ligne contient $n$ entiers $m$ ($1 \le m \le 100$), leur définition est celle indiquée ci-dessus. La ligne suivante contient quatre entiers $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$), indiquant la position du $i$-ème modèle de météore dans les deux photos.

Sortie

Pour chaque cas de test, sortez une ligne de $n$ nombres réels, tels que définis ci-dessus. Supposons que votre réponse soit $x$ et la réponse du jury soit $y$, votre réponse est considérée comme correcte si et seulement si $\frac{|x - y|}{\max(y, 1)} < 10^{-6}$.

Exemples

Entrée 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

Sortie 1

2.000000000 2.000000000
3.000000000 4.000000000 3.000000000

Remarque 1

Pour le premier cas de test, la force gravitationnelle maximale du modèle de météore 1 et du modèle de météore 2 se produit lorsqu'ils atteignent (0.5,0) et (0.5, 1) respectivement. À ce moment, la réponse est $\frac{m_1 m_2}{m_1 m_2 \min(D_t^2(1,2))} = \frac{1}{\min(D_t^2(1,2))} = 2$.

Picture 2: Two test cases