קאמומה מתעניין מאוד בתצפית על מטאורים. הוא יצר מודל דו-ממדי אינסופי המדמה את תנועתם של מטאורים (אף על פי שהוא למעשה לא מדמה שום דבר). ישנם $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$.