يهتم كامومي كثيرًا برصد الشهب. لقد أنشأ نموذجًا ثنائي الأبعاد لا نهائي الحجم يحاكي حركة الشهب (على الرغم من أنه لا يحاكي أي شيء في الواقع). يوجد $n$ من نماذج الشهب في هذه المحاكاة، ووزن نموذج الشهاب رقم $i$ هو $m_i$. يتحرك كل نموذج شهاب بسرعة ثابتة على طول خط مستقيم ثابت (وقد يكون ساكنًا أيضًا).

لقد مر وقت طويل منذ أن قام كامومي بتشغيل هذا النموذج. في أحد الأيام، خطرت لكامومي فكرة مفاجئة والتقط صورتين للنموذج الحالي. باعتبار موقع كامومي هو نقطة الأصل، فإنه لكل صورة $i$ ($i = 1, 2$)، كان نموذج الشهاب رقم $j$ يقع عند الموضع $(x_{i,j}, y_{i,j})$ في المستوي.

يمكنك حساب مسار كل نموذج شهاب، لكن هذا لا يكفي! يريد منك كامومي أن تحسب، لكل نموذج شهاب $i$، أقصى قوة جاذبية يؤثر بها أي نموذج شهاب آخر عليه طوال فترة عمل النموذج بأكملها (يمكنك اعتبار ذلك بمثابة مقدار لا نهائي من الوقت قبل وبعد التقاط الصور).

لاحظ أنه يمكن إعادة كتابة صيغة الجاذبية المعتادة على الشكل $F = G \frac{m_1 m_2}{r^2} = \frac{G}{\frac{1}{m_1} \frac{1}{m_2} r^2}$. لتجنب التعامل مع بعض الحالات الحدية، يعطيك كامومي بدلاً من ذلك $m'_i = \frac{1}{m_i}$ كمدخل، وتحتاج فقط إلى طباعة نتيجة قسمة الإجابة على $G$ ثم أخذ المقلوب. أي أنه لكل $i$، احسب $\min_{j \ne i} \min_{t \in \mathbb{R}} m'_i m'_j D_t^2(i, j)$، حيث $D_t(i, j)$ هي المسافة بين نموذجي الشهابين $i$ و$j$ عند الزمن $t$، ويمكن أن يكون $t$ أي عدد حقيقي (سالبًا أو موجبًا أو صفرًا).

الإدخال

يحتوي كل اختبار على عدة حالات اختبار. السطر الأول يحتوي على عدد صحيح واحد $t$ ($1 \le t \le 10^4$)، يشير إلى عدد حالات الاختبار. يلي ذلك وصف حالات الاختبار.

السطر الأول يحتوي على عدد صحيح واحد $n$ ($2 \le n, \sum n \le 10^5$)، يشير إلى عدد نماذج الشهب.

السطر الثاني يحتوي على $n$ من الأعداد الصحيحة $m'_i$ ($1 \le m'_i \le 100$)، وتعريفها كما هو مذكور أعلاه.

الأسطر الـ $n$ التالية يحتوي كل سطر منها على أربعة أعداد صحيحة $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$)، تشير إلى موضع نموذج الشهاب رقم $i$ في الصورتين.

الإخراج

لكل حالة اختبار، اطبع سطرًا واحدًا يحتوي على $n$ من الأعداد الحقيقية، كما هو محدد أعلاه.

بفرض أن إجابتك هي $x$ وإجابة لجنة التحكيم هي $y$، تُعتبر إجابتك صحيحة إذا وفقط إذا كان $\frac{|x - y|}{\max(y, 1)} \le 10^{-6}$.

أمثلة

الإدخال 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

الإخراج 1

2.000000000 2.000000000
3.000000000 4.000000000 3.000000000

ملاحظة

بالنسبة لحالة الاختبار الأولى، تحدث أقصى قوة جاذبية بين نموذج الشهاب 1 ونموذج الشهاب 2 عندما يصلان إلى $(0.5, 0)$ و$(0.5, 1)$ على التوالي. عند هذه النقطة، تكون الإجابة هي $m'_1 m'_2 d_{\min}^2 = 2$.