Wish upon a shooting star

The mysterious organization JAG (Japanese Alumni Group) holds meetings on a regular basis. One day the topic was "how to enable the participating teams to perform at their best in the upcoming ICPC (International Collegiate Programming Contest) domestic preliminary round." The conclusion of the meeting was to wish each team good luck upon shooting stars, and they went up to the roof of the building that houses their headquarters.

When they reached the roof, $n$ shooting stars were visible in the sky. A shooting star is represented as a sphere in three-dimensional space, and the stars are numbered $1$ through $n$. A member knowledgeable about stars determined that each shooting star can be regarded as moving in a straight line at a constant speed while its radius shrinks at a constant rate. Actual measurements gave the initial position $(px\_i, py\_i, pz\_i)$, the velocity $(vx\_i, vy\_i, vz\_i)$, the initial radius $r\_i$, and the shrink rate $vr\_i$ of each shooting star. This means that at time $t$ ($t \geq 0$) shooting star $i$ is a sphere with center $(px\_i + t vx\_i, py\_i + t vy\_i, pz\_i + t vz\_i)$ and radius $r\_i - t vr\_i$. A shooting star vanishes on its own the moment its radius becomes 0. Also, if two shooting stars touch, both of them vanish.

Your job is to determine, so that they can wish the participating teams good luck efficiently, the time until each shooting star vanishes. Since some of them have outstanding eyesight, you do not need to consider the possibility of shooting stars other than the given $n$. In addition, they observed the shooting stars very efficiently, so you may consider the time spent observing to be negligibly small.

The input consists of multiple datasets, and the number of datasets in one input is at most 100. The format of each dataset is as follows.

$n$

$px\_1$ $py\_1$ $pz\_1$ $vx\_1$ $vy\_1$ $vz\_1$ $r\_1$ $vr\_1$

...

$px\_n$ $py\_n$ $pz\_n$ $vx\_n$ $vy\_n$ $vz\_n$ $r\_n$ $vr\_n$

$n$ is an integer representing the number of shooting stars, and you may assume $1 \leq n \leq 200$.

The following $n$ lines give the information about the shooting stars. Each line contains 8 values with 4 digits after the decimal point, where $(px\_i, py\_i, pz\_i)$ is the initial position of shooting star $i$, $(vx\_i, vy\_i, vz\_i)$ is its velocity, $r\_i$ is its initial radius, and $vr\_i$ is its shrink rate. For the given values you may assume $-1{,}000 \leq px\_i \leq 1{,}000$, $-1{,}000 \leq py\_i \leq 1{,}000$, $-1{,}000 \leq pz\_i \leq 1{,}000$, $-100 \leq vx\_i \leq 100$, $-100 \leq vy\_i \leq 100$, $-100 \leq vz\_i \leq 100$, $1 \leq r\_i \leq 100$, and $1 \leq vr\_i \leq 100$.

For each given dataset you may also assume the following.

• Even if the initial radius of one shooting star changes by $10^{-8}$, the set of pairs of stars that touch does not change.
• Even if one shooting star is assumed not to vanish by touching, it does not touch two or more shooting stars within $10^{-8}$ of time, nor does it vanish on its own within $10^{-8}$ of the time it touches another shooting star.
• In the initial state no two shooting stars overlap, and they are at least $10^{-8}$ apart.
• At time $t < 10^{-8}$, no two shooting stars touch.

$n = 0$ marks the end of the input. It is not included in the datasets.

For each dataset, output the time until each shooting star vanishes, one per line, in order starting from shooting star 1.

The output must not have an absolute error greater than $10^{-8}$.

Do not output any other extra characters.