Kamome está muy interesado en la observación de meteoros. Ha creado un modelo bidimensional infinitamente grande que simula el movimiento de los meteoros (aunque en realidad no simula nada). Hay $n$ modelos de meteoros en esta simulación, y el peso del $i$-ésimo modelo de meteoro es $m_i$. Cada modelo de meteoro se mueve a una velocidad constante a lo largo de una línea recta fija (también puede estar estacionario).

Hace mucho tiempo que Kamome no ha ejecutado este modelo. Un día, Kamome tuvo una idea repentina y tomó dos fotos del modelo actual. Tomando la posición de Kamome como origen, para cada foto $i$ ($i=1, 2$), el $j$-ésimo modelo de meteoro estaba ubicado en la posición $(x_{i,j}, y_{i,j})$ en el plano.

Puedes calcular la trayectoria de cada modelo de meteoro, ¡pero no es suficiente! Kamome quiere que calcules, para cada modelo de meteoro $i$, la fuerza gravitacional máxima que otro modelo de meteoro le ejerce durante toda la duración de la ejecución del modelo (puedes considerar esto como una cantidad infinita de tiempo antes y después de tomar las fotos).

Observa que la fórmula gravitacional habitual puede reescribirse como $F = G \frac{m_1 m_2}{D^2}$. Para evitar tratar algunos casos particulares, Kamome te da en su lugar $\frac{m_1 m_2}{G}$ como entrada, y solo debes imprimir el resultado de dividir la respuesta por $G$ y luego tomar el inverso. Es decir, para cada $i$, calcula $\min_{j \neq i} \min_{t \in \mathbb{R}} \frac{1}{m_i m_j D_t^2(i, j)}$, donde $D_t(i, j)$ es la distancia entre los modelos de meteoros $i$ y $j$ en el tiempo $t$, y $t$ puede ser cualquier número real (negativo, positivo o cero).

Imagen 1: Hoshizora

Entrada

Cada caso de prueba contiene varios casos de prueba. La primera línea contiene un entero $t$ ($1 \le t \le 10^4$), que indica el número de casos de prueba. A continuación se describe cada caso de prueba.

La primera línea contiene dos enteros $n$ ($2 \le n, \sum n \le 10^5$), que indican el número de modelos de meteoros. La segunda línea contiene $n$ enteros $m$ ($1 \le m \le 100$), su definición es la indicada anteriormente. Las siguientes $n$ líneas contienen cuatro enteros cada una: $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$), que indican la posición del $i$-ésimo modelo de meteoro en las dos fotos.

Salida

Para cada caso de prueba, imprime una línea de $n$ números reales, según lo definido anteriormente. Supongamos que tu respuesta es $x$ y la respuesta del jurado es $y$, tu respuesta se considera correcta si y solo si $\frac{|x - y|}{\max(y, 1)} < 10^{-6}$.

Ejemplos

Entrada 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

Salida 1

2.000000000 2.000000000
3.000000000 4.000000000 3.000000000

Nota 1

Para el primer caso de prueba, la fuerza gravitacional máxima del modelo de meteoro 1 y del modelo de meteoro 2 ocurre cuando alcanzan (0.5,0) y (0.5, 1) respectivamente. En ese momento, la respuesta es $\frac{m_1 m_2}{m_1 m_2 \min(D_t^2(1,2))} = \frac{1}{\min(D_t^2(1,2))} = 2$.

Imagen 2: Dos casos de prueba