Wish upon a shooting star

謎の組織 JAG (Japanese Alumni Group) では定期的に会議を開いている．ある日の議題は「近日行われる ICPC (International Collegiate Programming Contest) 国内予選で参加チームが力を発揮できるようにするには」であった．会議の結論として流れ星に各チームの健闘を祈ることになり，彼らは本部を置く建物の屋上に出た．

彼らが屋上に出ると，空には $n$ 個の流れ星が見えていた．流れ星は3次元空間上の球として表され，$1$ から $n$ の番号が割り振られている．星に詳しいメンバーにより，各流れ星は一定の速度で直線的に移動すると同時に，一定の速度で半径が小さくなっていくとみなせることが分かった．実際に測定してみたところ，各流れ星の初期位置 $(px\_i, py\_i, pz\_i)$，移動速度 $(vx\_i, vy\_i, vz\_i)$，初期半径 $r\_i$，消滅速度 $vr\_i$ が分かった．これは流れ星 $i$ が時刻 $t$ ($t \geq 0$) で中心座標 $(px\_i + t vx\_i, py\_i + t vy\_i, pz\_i + t vz\_i)$，半径 $r\_i – t vr\_i$ の球となる事を表している．流れ星は，半径が 0 になった瞬間に自然消滅してしまう．また，2つの流れ星が接触した場合はどちらの流れ星も消滅してしまう．

あなたの仕事は，効率よく参加チームの健闘を祈ることができるように，各流れ星が消滅するまでの時間を求めることである．彼らの中には卓越した視力の持ち主がいるため，情報が与えられた $n$ 個以外に流れ星が存在する可能性については考慮しなくても良い．加えて，彼らは非常に効率よく流れ星の観測を行ったため，観測にかかった時間は無視できるほど小さいと考えて良い．

入力は複数のデータセットから構成され，1つの入力に含まれるデータセットの数は100以下である． 各データセットの形式は次の通りである．

$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$ は流れ星の数を表す整数であり，$1$ 以上 $200$ 以下と仮定して良い．

続く $n$ 行には流れ星の情報が与えられる． 各行は小数点以下4桁で表される8つの値を含み，$(px\_i, py\_i, pz\_i)$ は流れ星 $i$ の初期位置を，$(vx\_i, vy\_i, vz\_i)$ は移動速度を，$r\_i$ は初期半径を，$vr\_i$ は消滅速度をそれぞれ表す． 与えられる値について，$-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$，$1 \leq vr\_i \leq 100$ であると仮定して良い．

また，与えられるデータセットについて以下を仮定して良い．

• ある1つの流れ星の初期半径が $10^{-8}$ 変化しても，接触する星のペアの集合は変わらない
• ある1つの流れ星が接触により消滅しないと仮定しても，$10^{-8}$ 以内の時間で2つ以上の流れ星に接触したり，他の流れ星と接触する時刻から$10^{-8}$以内に自然消滅することはない
• 初期状態ではどの2つの流れ星も重なっておらず，$10^{-8}$以上の距離を空けている
• 時刻 $t < 10^{-8}$ ではどの2つの流れ星も接触しない

$n = 0$ は入力の終わりを示す．これはデータセットには含めない．

各データセットについて，各流れ星が消滅するまでの時間を流れ星1から順にそれぞれ1行に出力しなさい．

出力には$10^{-8}$を超える絶対誤差があってはならない．

それ以外の余計な文字を出力してはならない．