KND Warp

Problem

KND君は会津大学に在籍する学生プログラマだ。彼はその優秀な頭脳をもってワープ装置を開発したことで有名である。ワープ装置とは便利なもので、ある場所から別の場所まで瞬時に移動することができる。彼はこれから地球上に点在するワープ装置を用いて様々な場所を可能な限り早くめぐる旅を計画している。

彼の隣人であるあなたの仕事は3次元空間 (xyz直交座標系) 上に存在するN個のワープ装置をうまく使用して、1からMまでの番号がふられたM個の点を順に通って、M番目の点まで移動するときの最小の所要時間を求めることだ。はじめは1番目の点にいるものとし、どのワープ装置も任意のワープ装置へ時間0で移動できる。ワープ以外の単位距離の移動は単位時間を要する。経由点のクエリはQ個与えられる。

Input

入力は複数のテストケースからなる。 ひとつのテストケースは以下の形式で与えられる。 入力の終わりをN = Q = 0のとき示す。

N Q
x1 y1 z1
x2 y2 z2
...
xN yN zN
M1
x1,1 y1,1 z1,1
x1,2 y1,2 z1,2
...
x1,M y1,M z1,M

M2
x2,1 y2,1 z2,1
x2,2 y2,2 z2,2
...
x2,M y2,M z2,M
...
MQ
xQ,1 yQ,1 zQ,1
xQ,2 yQ,2 zQ,2
...
xQ,M yQ,M zQ,M

ここで、

• N:ワープ装置の数
• Q:旅のクエリの数
• M_i:i番目クエリの旅で訪れる点の数
• x_i,j,y_i,j,z_i,j:i番目のクエリの旅で訪れるj番目の点の座標(x,y,z)

である。

Constraints

入力は以下の条件を満たす。

• テストケースの数は15個を超えない。
• 入力の半分程度はN≤1000を満たす。
• 入力に含まれる値はすべて整数。
• 2≤N≤100,000
• 1≤Q≤1,000
• 2≤M≤100
• -1,000,000≤(全てのx,y,z座標値)≤1,000,000
• ワープ装置は上記の制約を満たす空間中にランダムに分布する(Sample Inputは例外)。
• ワープ装置同士、中継点同士、ワープ装置と中継点はそれぞれ重なることがある。

Output

各クエリにつき最小の所要時間を一行に出力せよ。この値はジャッジ出力の値と10^-4より大きい差を持ってはならない。

Sample Input

3 2
0 0 0
1 1 1
2 2 2
4
-1 -1 -1
3 3 3
-1 -1 -1
4 4 4
2
1234 5678 9012
1716 6155 9455
0 0

Sample Output

12.124355653
810.001234567

Notes

入力ファイルのサイズは4MB程度になる。入力は高速にしたほうがよいが、たとえばC++であればcinでも十分である。