Kamome rất quan tâm đến việc quan sát sao băng. Anh ấy đã tạo ra một mô hình hai chiều vô hạn mô phỏng chuyển động của các sao băng (mặc dù thực tế không mô phỏng gì cả). Có $n$ mô hình sao băng trong mô phỏng này, và khối lượng của mô hình sao băng thứ $i$ là $m_i$. Mỗi mô hình sao băng di chuyển với vận tốc không đổi dọc theo một đường thẳng cố định (cũng có thể đứng yên).

Đã rất lâu kể từ khi Kamome chạy mô hình này. Một ngày nọ, Kamome nảy ra một ý tưởng bất ngờ và chụp hai bức ảnh của mô hình hiện tại. Lấy vị trí của Kamome làm gốc tọa độ, với mỗi bức ảnh $i$ ($i = 1, 2$), mô hình sao băng thứ $j$ nằm tại vị trí $(x_{i, j}, y_{i, j})$ trên mặt phẳng.

Bạn có thể tính được quỹ đạo của mỗi mô hình sao băng, nhưng như thế vẫn chưa đủ! Kamome muốn bạn tính toán, với mỗi mô hình sao băng $i$, lực hấp dẫn lớn nhất mà một mô hình sao băng khác tác dụng lên nó trong suốt toàn bộ thời gian chạy mô hình (bạn có thể coi đây là khoảng thời gian vô hạn trước và sau khi chụp ảnh).

Lưu ý rằng công thức hấp dẫn thông thường có thể được viết lại thành $F = G \frac{m_1 m_2}{D^2}$. Để tránh xử lý một số trường hợp đặc biệt, Kamome cung cấp cho bạn $\frac{m_1 m_2}{G}$ làm đầu vào, và bạn chỉ cần in ra kết quả của việc chia đáp án cho $G$ rồi lấy nghịch đảo. Nghĩa là, với mỗi $i$, hãy tính $\min_{j \neq i} \min_{t \in \mathbb{R}} \frac{1}{m_i m_j D_t^2(i, j)}$, trong đó $D_t(i, j)$ là khoảng cách giữa các mô hình sao băng $i$ và $j$ tại thời điểm $t$, và $t$ có thể là bất kỳ số thực nào (âm, dương hoặc không).

Hình 1: Hoshizora

Dữ liệu vào

Mỗi test case chứa nhiều test case. Dòng đầu tiên chứa một số nguyên $t$ ($1 \le t \le 10^4$), cho biết số lượng test case. Mỗi test case được mô tả như sau.

Dòng đầu tiên chứa hai số nguyên $n$ ($2 \le n, \sum n \le 10^5$), cho biết số lượng mô hình sao băng. Dòng thứ hai chứa $n$ số nguyên $m$ ($1 \le m \le 100$), định nghĩa như đã nêu ở trên. $n$ dòng tiếp theo, mỗi dòng chứa bốn số nguyê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$), cho biết vị trí của mô hình sao băng thứ $i$ trong hai bức ảnh.

Dữ liệu ra

Với mỗi test case, in ra một dòng gồm $n$ số thực, theo định nghĩa ở trên. Giả sử đáp án của bạn là $x$ và đáp án của ban giám khảo là $y$, đáp án của bạn được coi là đúng nếu và chỉ nếu $\frac{|x - y|}{\max(y, 1)} < 10^{-6}$.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

2.000000000 2.000000000
3.000000000 4.000000000 3.000000000

Ghi chú 1

Với test case đầu tiên, lực hấp dẫn lớn nhất của mô hình sao băng 1 và mô hình sao băng 2 xảy ra khi chúng lần lượt đạt đến (0.5,0) và (0.5, 1). Tại thời điểm đó, đáp án là $\frac{m_1 m_2}{m_1 m_2 \min(D_t^2(1,2))} = \frac{1}{\min(D_t^2(1,2))} = 2$.

Hình 2: Hai test case