Kamome is very interested in observing meteors. He created an infinitely large two-dimensional model that simulates the movement of meteors (even though it doesn't actually simulate anything). There are $n$ meteor models in this simulation, and the weight of the $i$-th meteor model is $m_i$. Each meteor model moves at a constant speed along a fixed straight line (it might also be stationary).

It has been a long time since Kamome ran this model. One day, Kamome had a sudden idea and took two photos of the current model. Taking Kamome's position as the origin, for each photo $i$ ($i = 1, 2$), the $j$-th meteor model was located at the position $(x_{i,j}, y_{i,j})$ on the plane.

You can calculate the trajectory of each meteor model, but that's not enough! Kamome wants you to calculate, for each meteor model $i$, the maximum gravitational force that any other meteor model exerts on it during the entire time the model has been running (you can consider this as an infinite amount of time before and after the photos were taken).

Note that the usual gravitational formula can be rewritten as $F = G \frac{m_1 m_2}{r^2} = \frac{G}{\frac{1}{m_1} \frac{1}{m_2} r^2}$. To avoid dealing with some corner cases, Kamome instead gives you $m'_i = \frac{1}{m_i}$ as input, and you only need to output the result of dividing the answer by $G$ and then taking the reciprocal. That is, for each $i$, compute $\min_{j \ne i} \min_{t \in \mathbb{R}} m'_i m'_j D_t^2(i, j)$, where $D_t(i, j)$ is the distance between meteor models $i$ and $j$ at time $t$, and $t$ can be any real number (negative, positive, or zero).

Input

Each test contains multiple test cases. The first line contains one integer $t$ ($1 \le t \le 10^4$), indicating the number of test cases. The description of the test cases follows.

The first line contains one integer $n$ ($2 \le n, \sum n \le 10^5$), indicating the number of meteor models.

The second line contains $n$ integers $m'_i$ ($1 \le m'_i \le 100$), its definition is as stated above.

The next $n$ lines, each line contains four integers $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$), indicating the position of the $i$-th meteor model in the two photos.

Output

For each test case, output one line of $n$ real numbers, as defined above.

Assume your answer is $x$ and the jury's answer is $y$, your answer is considered correct if and only if $\frac{|x - y|}{\max(y, 1)} \le 10^{-6}$.

Examples

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

For the first test case, the maximum gravitational force of meteor model 1 and meteor model 2 occurs when they reach $(0.5, 0)$ and $(0.5, 1)$ respectively. At this point, the answer is $m'_1 m'_2 d_{\min}^2 = 2$.