Камоме дуже цікавиться спостереженням за метеорами. Він створив нескінченно велику двовимірну модель, яка імітує рух метеорів (хоча насправді вона нічого не імітує). У цій симуляції є $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$.