ACM International Collegiate Programming Contest
Japan Domestic, 2005-07-01

Problem E
Earth Observation with a Mobile Robot Team

地球環境観測用の新型移動ロボットが開発された． このロボットは，地面の上を動き回りながら，高性能センサーを用いてさまざまな観測データを収集する． また，近距離無線通信機能も備えており，近くのロボットとの間で観測データを交換することもできる． 自身の観測データや他のロボットから受信したデータを記憶しておくための大容量記憶装置も装備されている．

図1は，3台のロボットA, B, Cの位置とその電波が到達する範囲を図示したものである． 各円の中心がロボットの位置で，円の内側には電波が到達する． この図では，ロボットAとロボットBが，お互いに通信可能な位置におり，ロボットAからロボットB（およびその逆向き）に観測データを伝えることができる． 一方，ロボットCは離れた場所にいるため，ロボットAやロボットBと通信することはできない． しかし，図2のようにロボットBが移動してロボットCに接近すれば，ロボットBとロボットCの間で通信が可能となる． このようにして，ロボットAの観測データをロボットBが中継してロボットCに伝えることができる． 別の例として，図3のような配置の場合には，一瞬で多くのロボットにデータが伝わる．

図1: 3台のロボットの初期配置

図2: ロボットの移動による中継

図3: 複数ロボット間での一瞬の中継

以上の例からわかるように，ロボットがうまく移動すれば，観測データを短時間で多くのロボットに伝えることができる． あなたの仕事は，与えられたロボットの移動経路から，ロボット間で観測データがどのように伝わっていくかシミュレートするプログラムを作成することである． データのサイズにかかわらず，通信に要する時間は無視できると仮定すること．

Input

入力は複数のデータセットから構成され，各データセットは以下のような形式で与えられる．

N T R
ロボット1のニックネームと移動経路
ロボット2のニックネームと移動経路
...
ロボットNのニックネームと移動経路

N, T, R は 1 <=N <= 100, 1 <= T <= 1000, 1 <= R <= 10 を満たす整数であり，それぞれ，ロボットの台数，シミュレーション時間の上限，ロボットの電波が届く最大距離を表す．

各ロボットのニックネームと移動経路は以下のような形式で与えられる．

nickname
t₀ x₀ y₀
t₁ vx₁ vy₁
t₂ vx₂ vy₂
...
t_k vx_k vy_k

nickname は1文字以上8文字以下の英小文字の列であり，2台以上のロボットが同じニックネームを持つことはない． 残りはすべて整数であり，以下の条件を満たす．

0 = t₀ < t₁ < ... < t_k = T
-10 <= vx₁, vy₁, ..., vx_k, vy_k<= 10

ロボットは2次元平面上を移動する． (x₀, y₀) は時刻 0 のロボットの位置である． 時刻 t_i-1 から t_i の間(ただ し，0 < i <= k)，x 軸方向と y 軸方向に，それぞれ，速度 vx_i と vy_i でロボットは移動する． したがって，ロボットの軌跡は，2次元平面上の折れ線になる． なお，この折れ線は，自分自身と重なったり交差したりするかもしれない．

任意のデータセットが以下の条件を満たすと仮定してよい．

• 時刻 0 には，どの2台のロボット間の距離もちょうど R にはならない．
• ロボットの位置の x, y 座標は，常に-500以上，500以下の範囲に収まっている．
• 2台のロボットが距離 R + 10^-6 まで接近した場合には，その速度を保ったまま R - 10^-6 以内まで接近する．
• 2台のロボットが距離 R - 10^-6 まで離れた場合には，その速度を保ったまま R + 10^-6 以遠まで離れる．
• 時刻 t にある2台のロボットがちょうど距離 R まで接近し，時刻 t' に2台のロボット(前述のものと1台または2台が同じでもよい)がちょうど R まで離れたとすると，t と t' は，少なくとも 10^-6 単位時間離れている(すなわち，|t - t' | >= 10^-6)．

なお，複数のロボットが，同一時刻に同じ位置に存在するようなデータが入力 に含まれる可能性もある． そのような場合にも，ロボットは決められた速度で移動を続けることができる と仮定してプログラムを作成しなさい．

入力の終わりは 0 0 0 で表される．

Output

ロボット1は，時刻 0 に取得した観測データを，他のすべてのロボットに伝えようとする． 入力の各データセットに対して， その観測データが，時刻 T までに実際に伝達されるすべてのロボットのニックネームを，1行に一つずつ辞書式順序で出力しなさい． ニックネームの前後に空白のような余分な文字を含まないこと． ロボット1のニックネームは，必ず出力に含まれなければならないことに注意．

Sample Input

3 5 10
red
0 0 0
5 0 0
green
0 5 5
5 6 1
blue
0 40 5
5 0 0
3 10 5
atom
0 47 32
5 -10 -7
10 1 0
pluto
0 0 0
7 0 0
10 3 3
gesicht
0 25 7
5 -7 -2
10 -1 10
4 100 7
impulse
0 -500 0
100 10 1
freedom
0 -491 0
100 9 2
destiny
0 -472 0
100 7 4
strike
0 -482 0
100 8 3
0 0 0

Output for the Sample Input

blue
green
red
atom
gesicht
pluto
freedom
impulse
strike

First Input Data

ここに1番目のデータ がある．

The ACM ICPC