Камохэ очень интересуется наблюдением за метеорами. Он создал бесконечно большую двумерную модель, которая симулирует движение метеоров (хотя на самом деле ничего не симулирует). В этой симуляции есть $n$ моделей метеоров, и вес $i$-й модели метеора равен $m_i$. Каждая модель метеора движется с постоянной скоростью вдоль фиксированной прямой (она также может быть неподвижной).

Камохэ давно не запускал эту модель. Однажды ему внезапно пришла в голову идея, и он сделал два снимка текущей модели. Принимая положение Камохэ за начало координат, для каждого снимка $i$ ($i=1, 2$) $j$-я модель метеора находилась в точке $(x_{i,j}, y_{i,j})$ на плоскости.

Вы можете вычислить траекторию каждой модели метеора, но этого недостаточно! Камохэ хочет, чтобы вы для каждой модели метеора $i$ вычислили максимальную гравитационную силу, которую другая модель метеора оказывает на неё в течение всего времени выполнения модели (можно считать, что время простирается бесконечно как в прошлое, так и в будущее относительно моментов съёмки).

Обратите внимание, что обычная формула гравитации может быть переписана как $F = G \frac{m_1 m_2}{D^2}$. Чтобы избежать рассмотрения некоторых частных случаев, Камохэ даёт вам $\frac{m_1 m_2}{G}$ в качестве входных данных, и вам нужно вывести результат деления ответа на $G$ с последующим взятием обратной величины. То есть для каждого $i$ вычислите $\min_{j \neq i} \min_{t \in \mathbb{R}} \frac{1}{m_i m_j D_t^2(i, j)}$, где $D_t(i, j)$ – расстояние между моделями метеоров $i$ и $j$ в момент времени $t$, и $t$ может быть любым вещественным числом (отрицательным, положительным или нулём).

Изображение 1: Hoshizora

Входные данные

Каждый тестовый случай содержит несколько тестовых случаев. Первая строка содержит целое число $t$ ($1 \le t \le 10^4$), обозначающее количество тестовых случаев. Далее описывается каждый тестовый случай.

Первая строка содержит два целых числа $n$ ($2 \le n, \sum n \le 10^5$), обозначающих количество моделей метеоров. Вторая строка содержит $n$ целых чисел $m$ ($1 \le m \le 100$), их определение указано выше. Следующие $n$ строк содержат по четыре целых числа: $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$), обозначающих положение $i$-й модели метеора на двух снимках.

Выходные данные

Для каждого тестового случая выведите строку из $n$ вещественных чисел, как определено выше. Предположим, ваш ответ равен $x$, а ответ жюри равен $y$. Ваш ответ считается правильным тогда и только тогда, когда $\frac{|x - y|}{\max(y, 1)} < 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

Для первого тестового случая максимальная гравитационная сила для модели метеора 1 и модели метеора 2 достигается, когда они находятся в точках (0.5,0) и (0.5,1) соответственно. В этот момент ответ равен $\frac{m_1 m_2}{m_1 m_2 \min(D_t^2(1,2))} = \frac{1}{\min(D_t^2(1,2))} = 2$.

Изображение 2: Два тестовых случая