#include #include #include #include #include #include #define EPS (1e-12) using namespace std; struct robot_t { string name; int x0, y0; vector t, vx, vy; bool done; double t_get; }; int compare(double x, double y) { if(x - y > EPS) return +1; if(y - x > EPS) return -1; return 0; } double solve(int a, int b, int c, double lo, double hi) { if(compare(lo, 0.0) <= 0) lo = 0.0; if(a == 0) { assert(b == 0); return (c < 0) ? lo : HUGE_VAL; } if(b * b < a * c) return HUGE_VAL; double A = a; double B = b; double C = c; double x_lo = - (B + sqrt(B * B - A * C)) / A; double x_hi = - (B - sqrt(B * B - A * C)) / A; if(x_lo > x_hi) swap(x_lo, x_hi); if(compare(x_hi, lo) < 0) return HUGE_VAL; if(compare(x_lo, lo) <= 0) return lo; if(compare(x_lo, hi) <= 0) return min(x_lo, hi); return HUGE_VAL; } int main(void) { int N, T, R; while(cin >> N >> T >> R) { if(N == 0 && T == 0 && R == 0) break; vector r(N); for(int i = 0; i < N; i++) { int dmy; cin >> r[i].name >> dmy >> r[i].x0 >> r[i].y0; r[i].done = false; r[i].t_get = (i == 0) ? 0.0 : HUGE_VAL; while(true) { int t, vx, vy; cin >> t >> vx >> vy; r[i].t.push_back(t); r[i].vx.push_back(vx); r[i].vy.push_back(vy); if(t == T) break; } } while(true) { double t_min = HUGE_VAL; int i = N; for(int j = 0; j < N; j++) { if(!r[j].done && r[j].t_get < t_min) { i = j; t_min = r[j].t_get; } } if(i == N) break; for(int j = 0; j < N; j++) { if(i == j || r[j].done) continue; int p = 0, xi = r[i].x0, yi = r[i].y0; int q = 0, xj = r[j].x0, yj = r[j].y0; int t = 0; while(t < T) { int u = min(r[i].t[p], r[j].t[q]); if(u > t_min) { int dx1 = r[i].vx[p] - r[j].vx[q]; int dy1 = r[i].vy[p] - r[j].vy[q]; int dx2 = xi - xj; int dy2 = yi - yj; int a = dx1 * dx1 + dy1 * dy1; int b = dx1 * dx2 + dy1 * dy2; int c = dx2 * dx2 + dy2 * dy2 - R * R; double tmp = solve(a, b, c, t_min - t, u - t); r[j].t_get = min(r[j].t_get, tmp + t); } if(r[j].t_get <= u) break; xi += r[i].vx[p] * (u - t); yi += r[i].vy[p] * (u - t); xj += r[j].vx[q] * (u - t); yj += r[j].vy[q] * (u - t); if(r[i].t[p] == u) ++p; if(r[j].t[q] == u) ++q; t = u; } } r[i].done = true; } vector names; for(int i = 0; i < N; i++) { if(r[i].done) names.push_back(r[i].name); } sort(names.begin(), names.end()); for(int i = 0; i < names.size(); i++) { cout << names[i] << endl; } } return 0; }