KND君は会津大学に在籍する学生プログラマだ。彼はその優秀な頭脳をもってワープ装置を開発したことで有名である。ワープ装置とは便利なもので、ある場所から別の場所まで瞬時に移動することができる。彼はこれから地球上に点在するワープ装置を用いて様々な場所を可能な限り早くめぐる旅を計画している。
彼の隣人であるあなたの仕事は3次元空間 (xyz直交座標系) 上に存在するN個のワープ装置をうまく使用して、1からMまでの番号がふられたM個の点を順に通って、M番目の点まで移動するときの最小の所要時間を求めることだ。はじめは1番目の点にいるものとし、どのワープ装置も任意のワープ装置へ時間0で移動できる。ワープ以外の単位距離の移動は単位時間を要する。経由点のクエリはQ個与えられる。
入力は複数のテストケースからなる。 ひとつのテストケースは以下の形式で与えられる。 入力の終わりを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
ここで、
である。
入力は以下の条件を満たす。
各クエリにつき最小の所要時間を一行に出力せよ。この値はジャッジ出力の値と10-4より大きい差を持ってはならない。
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
12.124355653 810.001234567
入力ファイルのサイズは4MB程度になる。入力は高速にしたほうがよいが、たとえばC++であればcinでも十分である。