Kamome sangat tertarik mengamati meteor. Ia membuat sebuah model dua dimensi berukuran tak hingga yang menyimulasikan pergerakan meteor (meskipun sebenarnya model itu tidak menyimulasikan apa pun). Terdapat $n$ model meteor dalam simulasi ini, dan bobot dari model meteor ke-$i$ adalah $m_i$. Setiap model meteor bergerak dengan kelajuan konstan sepanjang sebuah garis lurus tetap (model tersebut juga bisa saja diam).

Sudah cukup lama sejak Kamome menjalankan model ini. Suatu hari, Kamome tiba-tiba mendapat ide dan mengambil dua foto dari model saat ini. Dengan mengambil posisi Kamome sebagai titik asal, untuk setiap foto $i$ ($i = 1, 2$), model meteor ke-$j$ berada pada posisi $(x_{i,j}, y_{i,j})$ pada bidang.

Anda dapat menghitung lintasan dari setiap model meteor, tetapi itu saja tidak cukup! Kamome ingin Anda menghitung, untuk setiap model meteor $i$, gaya gravitasi maksimum yang diberikan oleh model meteor lainnya terhadapnya selama seluruh waktu model tersebut berjalan (Anda dapat menganggap ini sebagai rentang waktu tak hingga sebelum dan sesudah foto diambil).

Perhatikan bahwa rumus gravitasi biasa dapat ditulis ulang sebagai $F = G \frac{m_1 m_2}{r^2} = \frac{G}{\frac{1}{m_1} \frac{1}{m_2} r^2}$. Untuk menghindari beberapa kasus ekstrem, Kamome sebagai gantinya memberikan $m'_i = \frac{1}{m_i}$ sebagai masukan, dan Anda hanya perlu mengeluarkan hasil pembagian jawaban tersebut dengan $G$ lalu diambil kebalikannya (resiprokal). Artinya, untuk setiap $i$, hitunglah $\min_{j \ne i} \min_{t \in \mathbb{R}} m'_i m'_j D_t^2(i, j)$, di mana $D_t(i, j)$ adalah jarak antara model meteor $i$ dan $j$ pada waktu $t$, dan $t$ dapat berupa bilangan riil apa pun (negatif, positif, atau nol).

Format Masukan

Setiap pengujian berisi beberapa kasus uji. Baris pertama berisi satu bilangan bulat $t$ ($1 \le t \le 10^4$), yang menyatakan banyaknya kasus uji. Deskripsi dari masing-masing kasus uji menyusul.

Baris pertama berisi satu bilangan bulat $n$ ($2 \le n, \sum n \le 10^5$), yang menyatakan banyaknya model meteor.

Baris kedua berisi $n$ bilangan bulat $m'_i$ ($1 \le m'_i \le 100$), yang definisinya seperti dinyatakan di atas.

$n$ baris berikutnya masing-masing berisi empat bilangan bulat $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$), yang menyatakan posisi model meteor ke-$i$ pada kedua foto tersebut.

Format Keluaran

Untuk setiap kasus uji, keluarkan satu baris yang berisi $n$ bilangan riil, sebagaimana didefinisikan di atas.

Misalkan jawaban Anda adalah $x$ dan jawaban juri adalah $y$, jawaban Anda dianggap benar jika dan hanya jika $\frac{|x - y|}{\max(y, 1)} \le 10^{-6}$.

Contoh

Masukan 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

Keluaran 1

2.000000000 2.000000000
3.000000000 4.000000000 3.000000000

Catatan

Untuk kasus uji pertama, gaya gravitasi maksimum antara model meteor 1 dan model meteor 2 terjadi ketika keduanya masing-masing mencapai $(0.5, 0)$ dan $(0.5, 1)$. Pada titik ini, jawabannya adalah $m'_1 m'_2 d_{\min}^2 = 2$.