Problem: A new type of mobile robot has been developed for environmental earth observation. It moves around on the ground, acquiring and recording various sorts of observational data using high precision sensors. Robots of this type have short range wireless communication devices and can exchange observational data with ones nearby. They also have large capacity memory units, on which they record data observed by themselves and those received from others.

Figure 1 illustrates the current positions of three robots A, B, and C and the geographic coverage of their wireless devices. Each circle represents the wireless coverage of a robot, with its center representing the position of the robot. In this figure, two robots A and B are in the positions where A can transmit data to B, and vice versa. In contrast, C cannot communicate with A or B, since it is too remote from them. Still, however, once B moves towards C as in Figure 2, B and C can start communicating with each other. In this manner, B can relay observational data from A to C. Figure 3 shows another example, in which data propagate among several robots instantaneously.

<image>
---
Figure 1: The initial configuration of three robots
<image>
---
Figure 2: Mobile relaying
<image>
---
Figure 3: Instantaneous relaying among multiple robots

As you may notice from these examples, if a team of robots move properly, observational data quickly spread over a large number of them. Your mission is to write a program that simulates how information spreads among robots. Suppose that, regardless of data size, the time necessary for communication is negligible.



Input

The input consists of multiple datasets, each in the following format.

> N T R
>  nickname and travel route of the first robot
>  nickname and travel route of the second robot
>  ...
>  nickname and travel route of the N-th robot
>

The first line contains three integers N, T, and R that are the number of robots, the length of the simulation period, and the maximum distance wireless signals can reach, respectively, and satisfy that 1 <=N <= 100, 1 <= T <= 1000, and 1 <= R <= 10.

The nickname and travel route of each robot are given in the following format.

> nickname
>  t0 x0 y0
>  t1 vx1 vy1
>  t2 vx2 vy2
>  ...
>  tk vxk vyk
>

Nickname is a character string of length between one and eight that only contains lowercase letters. No two robots in a dataset may have the same nickname. Each of the lines following nickname contains three integers, satisfying the following conditions.

> 0 = t0 < t1 < ... < tk = T
>  -10 <= vx1, vy1, ..., vxk, vyk<= 10
>

A robot moves around on a two dimensional plane. (x0, y0) is the location of the robot at time 0. From time ti-1 to ti (0 < i <= k), the velocities in the x and y directions are vxi and vyi, respectively. Therefore, the travel route of a robot is piecewise linear. Note that it may self-overlap or self-intersect.

You may assume that each dataset satisfies the following conditions.

* The distance between any two robots at time 0 is not exactly R.
* The x- and y-coordinates of each robot are always between -500 and 500, inclusive.
* Once any robot approaches within R + 10-6 of any other, the distance between them will become smaller than R - 10-6 while maintaining the velocities.
* Once any robot moves away up to R - 10-6 of any other, the distance between them will become larger than R + 10-6 while maintaining the velocities.
* If any pair of robots mutually enter the wireless area of the opposite ones at time t and any pair, which may share one or two members with the aforementioned pair, mutually leave the wireless area of the opposite ones at time t', the difference between t and t' is no smaller than 10-6 time unit, that is, |t - t' | >= 10-6.


A dataset may include two or more robots that share the same location at the same time. However, you should still consider that they can move with the designated velocities.

The end of the input is indicated by a line containing three zeros.

Output

For each dataset in the input, your program should print the nickname of each robot that have got until time T the observational data originally acquired by the first robot at time 0. Each nickname should be written in a separate line in dictionary order without any superfluous characters such as leading or trailing spaces.

Example

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

blue
green
red
atom
gesicht
pluto
freedom
impulse
strike

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
//#define EPS 0.000000001
using namespace std;


#define EPS 0.000000001
#define NUM 105

struct Point{
	Point(){
		x = y = 0;
	}
	Point(int arg_x,int arg_y){
		x = arg_x;
		y = arg_y;
	}
	ll x,y;
};
typedef Point Vector;


struct Data{
	Data(ll arg_Time,ll arg_Vx,ll arg_Vy){
		Time = arg_Time;
		Vx = arg_Vx;
		Vy = arg_Vy;
	}
	ll Time,Vx,Vy;
};

struct Info{

	Point pos_First;
	string name;
	vector<Data> V;
};

struct State{
	State(int arg_robo_A,int arg_robo_B,double arg_Time){
		robo_A = arg_robo_A;
		robo_B = arg_robo_B;
		Time = arg_Time;
	}
	bool operator<(const struct State &arg) const{
		return Time > arg.Time; //時刻の昇順(PQ)
	}

	int robo_A,robo_B;
	double Time;
};

int N;
ll T,R;
bool is_adj[NUM][NUM],is_Same[NUM];
Info info[NUM];
priority_queue<State> Q;



int calc_dist(Point A,Point B){

	return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);
}

void calc_Cross_Time(int robo_A,int robo_B){

	Point pos_A = info[robo_A].pos_First;
	Point pos_B = info[robo_B].pos_First;

	Vector v_A = Vector(info[robo_A].V[0].Vx,info[robo_A].V[0].Vy);
	Vector v_B = Vector(info[robo_B].V[0].Vx,info[robo_B].V[0].Vy);
	Vector next_v_A,next_v_B;

	int index_A = 0,index_B = 0;

	ll current_Time = 0,next_Time;

	while(true){

		next_v_A = v_A;
		next_v_B = v_B;

		//次のイベントはどちらが早いか、または同時か

		if(	(index_A < info[robo_A].V.size()-1 && info[robo_A].V[index_A].Time < info[robo_B].V[index_B].Time)){ //Aが早い

			next_Time = info[robo_A].V[index_A].Time;

			next_v_A.x = info[robo_A].V[index_A+1].Vx;
			next_v_A.y = info[robo_A].V[index_A+1].Vy;

			index_A++;

		}else if((index_B < info[robo_B].V.size()-1 && info[robo_B].V[index_B].Time < info[robo_A].V[index_A].Time)){ //Bが早い

			next_Time = info[robo_B].V[index_B].Time;

			next_v_B.x = info[robo_B].V[index_B+1].Vx;
			next_v_B.y = info[robo_B].V[index_B+1].Vy;

			index_B++;

		}else{ //同時

			next_Time = info[robo_A].V[index_A].Time;

			if(index_A+1 <= info[robo_A].V.size()-1){

				next_v_A.x = info[robo_A].V[index_A+1].Vx;
				next_v_A.y = info[robo_A].V[index_A+1].Vy;
				index_A++;
			}

			if(index_B+1 <= info[robo_B].V.size()-1){

				next_v_B.x = info[robo_B].V[index_B+1].Vx;
				next_v_B.y = info[robo_B].V[index_B+1].Vy;
				index_B++;
			}
		}

		//判別式
		ll a = (v_A.x-v_B.x)*(v_A.x-v_B.x)+(v_A.y-v_B.y)*(v_A.y-v_B.y);
		ll b = 2*((pos_A.x-pos_B.x)*(v_A.x-v_B.x)+(pos_A.y-pos_B.y)*(v_A.y-v_B.y));
		ll c = (pos_A.x-pos_B.x)*(pos_A.x-pos_B.x)+(pos_A.y-pos_B.y)*(pos_A.y-pos_B.y)-R*R;

		ll D = b*b-4*a*c;

		if(a != 0  && D >= 0){ //解があるならそれを求める:current_Time-next_Timeの間にあれば、それをQにpush

			double A = a,B = b, C = c;
			double CURRENT = current_Time,NEXT = next_Time;

			double t_1 = CURRENT+(-B-sqrt(B*B-4*A*C))/(2*A);
			double t_2 = CURRENT+(-B+sqrt(B*B-4*A*C))/(2*A);


			if(t_1 > CURRENT+EPS && t_1+EPS < NEXT){

				Q.push(State(robo_A,robo_B,t_1));

			}
			if(fabs(t_1-t_2) > EPS && t_2 > CURRENT+EPS && t_2+EPS < NEXT){

				Q.push(State(robo_A,robo_B,t_2));
			}
		}

		if(index_A == info[robo_A].V.size()-1 && index_B == info[robo_B].V.size()-1){

			break;
		}

		pos_A.x += v_A.x*(next_Time-current_Time);
		pos_A.y += v_A.y*(next_Time-current_Time);

		pos_B.x += v_B.x*(next_Time-current_Time);
		pos_B.y += v_B.y*(next_Time-current_Time);

		current_Time = next_Time;

		v_A = next_v_A;
		v_B = next_v_B;
	}
}

void func(){

	for(int i = 0; i < NUM; i++){

		info[i].V.clear();
	}

	int base_robot = 0;

	ll Time,Vx,Vy;

	for(int i = 0; i < N; i++){

		cin >> info[i].name;

		scanf("%lld %lld %lld",&Time,&info[i].pos_First.x,&info[i].pos_First.y);

		while(true){

			scanf("%lld %lld %lld",&Time,&Vx,&Vy);
			info[i].V.push_back(Data(Time,Vx,Vy));

			if(Time == T)break;
		}
	}

	is_Same[base_robot] = true;
	for(int i = 1; i < N; i++){

		is_Same[i] = false;
	}

	for(int i = 0; i < N; i++){
		for(int k = 0; k < N; k++){

			is_adj[i][k] = (i==k);
		}
	}

	//最初の位置関係
	for(int a = 0; a < N-1; a++){
		for(int b = a+1; b < N; b++){
			//最初の距離
			ll first_dist = calc_dist(info[a].pos_First,info[b].pos_First);

			if(first_dist <= R*R){
				is_adj[a][b] = true;
				is_adj[b][a] = true;
			}
		}
	}

	for(int mid = 0; mid < N; mid++){
		for(int start = 0; start < N; start++){
			if(!is_adj[start][mid])continue;
			for(int goal = 0; goal < N; goal++){
				if(!is_adj[mid][goal])continue;

				is_Same[goal] = is_Same[start]|is_Same[mid];
			}
		}
	}


	for(int a = 0; a < N-1; a++){
		for(int b = a+1; b < N; b++){

			calc_Cross_Time(a,b);
		}
	}

	while(!Q.empty()){

		if(is_adj[Q.top().robo_A][Q.top().robo_B]){

			is_adj[Q.top().robo_A][Q.top().robo_B] = false;
			is_adj[Q.top().robo_B][Q.top().robo_A] = false;

		}else{

			is_adj[Q.top().robo_A][Q.top().robo_B] = true;
			is_adj[Q.top().robo_B][Q.top().robo_A] = true;

			if(is_Same[Q.top().robo_A] == is_Same[Q.top().robo_B]){
				Q.pop();
				continue;
			}

			int robo_id;

			if(is_Same[Q.top().robo_A]){

				robo_id = Q.top().robo_B;

			}else{

				robo_id = Q.top().robo_A;
			}

			is_Same[robo_id] = true;

			queue<int> calc_Q;
			calc_Q.push(robo_id);

			while(!calc_Q.empty()){

				for(int i = 0; i < N; i++){

					if(is_adj[calc_Q.front()][i] == true && is_Same[i] ==false){

						is_Same[i] = true;
						calc_Q.push(i);
					}
				}
				calc_Q.pop();
			}
		}

		Q.pop();
	}

	vector<string> ans;

	for(int i = 0; i < N; i++){

		if(is_Same[i]){

			ans.push_back(info[i].name);
		}
	}

	sort(ans.begin(),ans.end());

	for(int i = 0; i < ans.size(); i++){

		printf("%s\n",ans[i].c_str());
	}
}

int main(){

	while(true){

		scanf("%d %lld %lld",&N,&T,&R);
		if(N == 0 && T == 0 && R == 0)break;

		func();
	}

	return 0;
}