Earth Observation with a Mobile Robot Team

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 any robot nearby. They also have large-capacity memory units on which they record both the data they observe themselves and the data received from others.

Consider three robots A, B, and C, each with a circular wireless coverage area centered at its current position. Suppose A and B are close enough that A can transmit data to B and vice versa, while C is too remote to communicate with either. If B then moves toward C, B and C can start communicating, so B can relay observational data from A to C. In this way, if a team of robots moves properly, observational data quickly spreads over a large number of them.

Two robots can communicate at any instant when the distance between them is at most $R$. Communication and relaying are instantaneous, so at any moment the data held by one robot immediately reaches every robot connected to it, directly or through intermediates. Your mission is to write a program that simulates how the data originally held by the first robot spreads among the team. Regardless of data size, assume the time necessary for communication is negligible.

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$: the number of robots, the length of the simulation period, and the maximum distance the wireless signal can reach. They satisfy $1 \le N \le 100$, $1 \le T \le 1000$, and $1 \le R \le 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 string of length between one and eight consisting only of lowercase letters. No two robots in a dataset share the same nickname. Each of the lines following the nickname contains three integers that satisfy:

• $0 = t_0 < t_1 < \dots < t_k = T$
• $-10 \le vx_1, vy_1, \dots, vx_k, vy_k \le 10$

A robot moves on a two-dimensional plane. $(x_0, y_0)$ is its location at time $0$. From time $t_{i-1}$ to $t_i$ (for $0 < i \le k$), its velocities in the $x$ and $y$ directions are $vx_i$ and $vy_i$, respectively. The travel route is therefore piecewise linear and may self-overlap or self-intersect.

Each dataset satisfies the following conditions:

• The distance between any two robots at time $0$ is never exactly $R$.
• The $x$- and $y$-coordinates of every robot are always between $-500$ and $500$, inclusive.
• Once any robot comes within $R + 10^{-6}$ of another, the distance between them becomes smaller than $R - 10^{-6}$ while the velocities are maintained.
• Once any robot moves apart to $R - 10^{-6}$ from another, the distance between them becomes larger than $R + 10^{-6}$ while the velocities are maintained.
• If one pair of robots mutually enter each other's wireless area at time $t$, and another pair (possibly sharing one or two members) mutually leave each other's wireless area at time $t'$, then $|t - t'| \ge 10^{-6}$.

Two or more robots may share the same location at the same time; they still move with their designated velocities.

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

For each dataset, print the nickname of every robot that has received, by time $T$, the observational data originally acquired by the first robot at time $0$. Print each nickname on its own line in dictionary order, with no leading or trailing spaces. The first robot itself always counts as having the data. The set of such robots is uniquely determined.