Kamome은 유성 관측에 많은 관심을 가지고 있습니다. 그는 유성들의 움직임을 시뮬레이션하는 (비록 실제로는 아무것도 시뮬레이션하지 않지만) 무한히 큰 2차원 모델을 만들었습니다. 이 시뮬레이션에는 $n$개의 유성 모델이 있으며, $i$번째 유성 모델의 질량은 $m_i$입니다. 각 유성 모델은 고정된 직선을 따라 일정한 속도로 이동합니다 (정지해 있을 수도 있습니다).

Kamome이 이 모델을 실행한 지 오랜 시간이 흘렀습니다. 어느 날, Kamome은 갑자기 아이디어가 떠올라 현재 모델의 사진 두 장을 찍었습니다. Kamome의 위치를 원점으로 하여, 각 사진 $i$ ($i=1, 2$)에서 $j$번째 유성 모델은 평면 상의 위치 $(x_{i,j}, y_{i,j})$에 있었습니다.

여러분은 각 유성 모델의 궤적을 계산할 수 있지만, 그것만으로는 충분하지 않습니다! Kamome은 각 유성 모델 $i$에 대해, 모델 실행 시간 전체 동안 (사진을 찍기 전과 후의 무한한 시간으로 간주할 수 있음) 다른 유성 모델이 이 유성 모델에 가하는 최대 중력을 계산하기를 원합니다.

일반적인 중력 공식은 $F = G \frac{m_1 m_2}{D^2}$로 다시 쓸 수 있습니다. 특수한 경우를 처리하지 않기 위해, Kamome은 대신 $\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)$는 시간 $t$에서 유성 모델 $i$와 $j$ 사이의 거리이며, $t$는 임의의 실수 (음수, 양수 또는 0)일 수 있습니다.

그림 1: 별하늘

입력

각 테스트 케이스는 여러 개의 테스트 케이스를 포함합니다. 첫 번째 줄에는 정수 $t$ ($1 \le t \le 10^4$)가 주어지며, 테스트 케이스의 개수를 나타냅니다. 이후 테스트 케이스들의 설명이 이어집니다.

첫 번째 줄에는 두 정수 $n$ ($2 \le n, \sum n \le 10^5$)이 주어지며, 유성 모델의 개수를 나타냅니다. 두 번째 줄에는 $n$개의 정수 $m$ ($1 \le m \le 100$)이 주어지며, 그 정의는 위에 설명된 대로입니다. 다음 줄에는 네 개의 정수 $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과 유성 모델 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: 두 개의 테스트 케이스