Kamome è molto interessato all'osservazione delle meteore. Ha creato un modello bidimensionale infinitamente grande che simula il movimento delle meteore (anche se in realtà non simula proprio nulla). Ci sono $n$ modelli di meteore in questa simulazione, e il peso dell'$i$-esimo modello di meteora è $m_i$. Ciascun modello di meteora si muove a velocità costante lungo una retta fissa (potrebbe anche essere fermo).

È passato molto tempo da quando Kamome ha avviato questo modello. Un giorno, Kamome ha avuto un'idea improvvisa e ha scattato due foto del modello attuale. Prendendo la posizione di Kamome come origine, per ciascuna foto $i$ ($i = 1, 2$), il $j$-esimo modello di meteora si trovava nella posizione $(x_{i,j}, y_{i,j})$ sul piano.

Puoi calcolare la traiettoria di ciascun modello di meteora, ma non basta! Kamome vuole che tu calcoli, per ciascun modello di meteora $i$, la massima forza gravitazionale che qualsiasi altro modello di meteora esercita su di esso durante l'intero tempo di funzionamento del modello (puoi considerarlo come un intervallo di tempo infinito prima e dopo lo scatto delle foto).

Nota che l'usuale formula gravitazionale può essere riscritta come $F = G \frac{m_1 m_2}{r^2} = \frac{G}{\frac{1}{m_1} \frac{1}{m_2} r^2}$. Per evitare di dover gestire alcuni casi limite, Kamome ti fornisce invece $m'_i = \frac{1}{m_i}$ come input, e tu devi solo stampare il risultato ottenuto dividendo la risposta per $G$ e prendendone poi il reciproco. Cioè, per ogni $i$, calcola $\min_{j \ne i} \min_{t \in \mathbb{R}} m'_i m'_j D_t^2(i, j)$, dove $D_t(i, j)$ è la distanza tra i modelli di meteora $i$ e $j$ al tempo $t$, e $t$ può essere qualsiasi numero reale (negativo, positivo o zero).

Input

Ogni test contiene più casi di test. La prima riga contiene un intero $t$ ($1 \le t \le 10^4$), che indica il numero di casi di test. Segue la descrizione dei casi di test.

La prima riga contiene un intero $n$ ($2 \le n, \sum n \le 10^5$), che indica il numero di modelli di meteore.

La seconda riga contiene $n$ interi $m'_i$ ($1 \le m'_i \le 100$), la cui definizione è quella riportata sopra.

Le successive $n$ righe contengono ciascuna quattro interi $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$), che indicano la posizione dell'$i$-esimo modello di meteora nelle due foto.

Output

Per ogni caso di test, stampa una riga di $n$ numeri reali, come definito sopra.

Assumendo che la tua risposta sia $x$ e la risposta della giuria sia $y$, la tua risposta è considerata corretta se e solo se $\frac{|x - y|}{\max(y, 1)} \le 10^{-6}$.

Esempi

Input 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

Output 1

2.000000000 2.000000000
3.000000000 4.000000000 3.000000000

Note

Per il primo caso di test, la massima forza gravitazionale tra il modello di meteora 1 e il modello di meteora 2 si verifica quando raggiungono rispettivamente $(0.5, 0)$ e $(0.5, 1)$. In questo punto, la risposta è $m'_1 m'_2 d_{\min}^2 = 2$.