描述

开发了一种用于环境地球观测的新型移动机器人。它在地面上移动，使用高精度传感器获取和记录各种观测数据。这种类型的机器人具有短距离无线通信设备，可以与附近的机器人交换观测数据。他们还有大容量存储单元，可以在这些存储单元上记录自己观察到的数据和从他人那里接收到的数据。

图 1 说明了三个机器人 $A$、$B$ 和 $C$ 的当前位置及其无线设备的地理覆盖范围。每个圆圈代表机器人的无线覆盖范围，其中心代表机器人的位置。在此图中，两个机器人 $A$ 和 $B$ 位于 $A$ 可以向 $B$ 传输数据的位置，反之亦然。相反，$C$ 无法与 $A$ 或 $B$ 通信，因为它离它们太远了。然而，一旦 $B$ 如图 2 所示向 $C$ 移动，$B$ 和 $C$ 就可以开始相互通信。通过这种方式，$B$ 可以将观测数据从 $A$ 中继到 $C$。图 3 显示了另一个示例，其中数据在多个机器人之间瞬间传播。

图 1：三个机器人的初始配置

图 2：移动中继

图 3：多个机器人之间的瞬时中继

从这些示例中您可能会注意到，如果一组机器人移动正常，则观察数据会迅速分布在大量机器人上。您的任务是编写一个程序来模拟信息如何在机器人之间传播。假设，无论数据大小如何，通信所需的时间都可以忽略不计。

输入

输入由多个数据集组成，每个数据集采用以下格式。

$N$ $T$ $R$ 第一个机器人的昵称和行驶路线 第二个机器人的昵称和行驶路线 ... 第 $N$ 个机器人的昵称和行驶路线

第一行包含三个整数 $N$、$T$ 和 $R$，分别是机器人数量、仿真周期长度和无线信号可以达到的最大距离，并满足 $1 \leq N \leq 100$、$1 \leq T \leq 1000$ 和 $1 \leq R \leq 10$。

每个机器人的昵称和行驶路线按以下格式给出。

昵称 $t0$ $x0$ $y0$ $t1$ $vx1$ $vy1$ $t2$ $vx2$ $vy2$ ... $tk$ $vxk$ $vyk$

昵称是长度介于 $1$ 到 $8$ 之间的字符串，仅包含小写字母。数据集中没有两个机器人可以具有相同的昵称。nickname 后面的每一行都包含三个整数，满足以下条件：

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

机器人在二维平面上移动。$(x_0, y_0)$ 是机器人在时间 $0$ 的位置。从时间 $t_{i-1}$ 到 $t_i$（$0 < i \leq k$），$x$ 和 $y$ 方向的速度分别为 $vx_i$ 和 $vy_i$。因此，机器人的行进路线是分段线性的。请注意，它可能会自重叠或自相交。

您可以假设每个数据集都满足以下条件：

1. 时间 $0$ 处任意两个机器人之间的距离并不正好是 $R$。
2. 每个机器人的 $x$ 坐标和 $y$ 坐标始终介于 $-500$ 和 $500$ 之间（包括 $-500$ 和 $500$）。
3. 一旦任何机器人接近 $R + 10^{-6}$ 以内，它们之间的距离将小于 $R - 10^{-6}$ 同时保持速度。
4. 一旦任何机器人离开，最高可达 $R - 10^{-6}$，它们之间的距离将大于 $R + 10^{-6}$ 同时保持速度。
5. 如果任意一对机器人在时间 $t$ 相互进入对面的无线区域，并且任何一对可能与上述对机器人共享一个或两个成员的机器人在时间 $t'$ 相互离开对面的机器人的无线区域，则 $t$ 和 $t'$ 之间的差值不小于 $10^{-6}$ 时间单位，即 $|t - t'| \geq 10^{-6}$。
6. 数据集可能包括两个或多个同时共享同一位置的机器人。但是，您仍应考虑到它们可以以指定的速度移动。

输入的结尾由包含三个 $0$ 的行表示。

输出

对于输入中的每个数据集，您的程序应打印每个机器人的昵称，这些机器人在时间 $T$ 之前获得了第一个机器人最初在时间 $0$ 获取的观测数据。每个昵称都应该按字典顺序写在单独的行中，不能有任何多余的字符，例如前导或尾随空格。

输入数据 1

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

输出数据 1

blue
green
red
atom
gesicht
pluto
freedom
impulse
strike

来源

日本 2005 国内