이동 로봇 팀을 이용한 지구 관측

환경 관측을 위한 새로운 이동 로봇이 개발되었다. 이 로봇은 지상을 돌아다니며 고정밀 센서로 다양한 관측 데이터를 수집하고 기록한다. 이런 로봇은 근거리 무선 통신 장치를 갖추고 있어 가까이 있는 다른 로봇과 관측 데이터를 주고받을 수 있으며, 대용량 메모리에 자신이 관측한 데이터와 다른 로봇에게서 받은 데이터를 모두 저장한다.

로봇 A, B, C 세 대가 각자 현재 위치를 중심으로 원형의 무선 통신 범위를 갖는다고 하자. A와 B는 서로 데이터를 주고받을 수 있을 만큼 가깝지만 C는 너무 멀리 있어 어느 쪽과도 통신할 수 없다고 하자. 이때 B가 C 쪽으로 이동하면 B와 C가 통신을 시작할 수 있으므로, B는 A의 관측 데이터를 C에게 중계할 수 있다. 이처럼 로봇 팀이 적절히 움직이면 관측 데이터는 순식간에 많은 로봇에게 퍼져 나간다.

두 로봇은 서로의 거리가 $R$ 이하인 순간이면 언제든 통신할 수 있다. 통신과 중계는 순간적으로 이루어지므로, 어느 순간에 한 로봇이 가진 데이터는 직접 또는 다른 로봇을 거쳐 그 로봇과 연결된 모든 로봇에게 즉시 전달된다. 첫 번째 로봇이 원래 가지고 있던 데이터가 로봇 팀 안에서 어떻게 퍼지는지 시뮬레이션하는 프로그램을 작성하여라. 데이터 크기와 관계없이 통신에 걸리는 시간은 무시할 수 있다고 가정한다.

입력은 여러 개의 데이터셋으로 이루어지며, 각 데이터셋의 형식은 다음과 같다.

N T R
첫 번째 로봇의 별명과 이동 경로
두 번째 로봇의 별명과 이동 경로
...
N번째 로봇의 별명과 이동 경로

첫 줄에는 세 정수 $N$, $T$, $R$이 주어진다. 각각 로봇의 수, 시뮬레이션 기간의 길이, 무선 신호가 도달할 수 있는 최대 거리이며 $1 \le N \le 100$, $1 \le T \le 1000$, $1 \le R \le 10$을 만족한다.

각 로봇의 별명과 이동 경로는 다음 형식으로 주어진다.

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

nickname은 소문자로만 이루어진 길이 1 이상 8 이하의 문자열이며, 한 데이터셋 안에서 같은 별명을 가진 로봇은 없다. 별명 다음 줄들에는 각각 세 정수가 주어지며 다음을 만족한다.

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

로봇은 2차원 평면 위를 움직인다. $(x_0, y_0)$은 시각 $0$에서의 위치이다. 시각 $t_{i-1}$부터 $t_i$까지($0 < i \le k$) $x$ 방향과 $y$ 방향의 속도는 각각 $vx_i$, $vy_i$이다. 따라서 이동 경로는 조각별 선형(piecewise linear)이며, 스스로 겹치거나 교차할 수 있다.

각 데이터셋은 다음 조건을 만족한다.

• 시각 $0$에서 임의의 두 로봇 사이의 거리는 정확히 $R$인 경우가 없다.
• 모든 로봇의 $x$좌표와 $y$좌표는 항상 $-500$ 이상 $500$ 이하이다.
• 어떤 로봇이 다른 로봇에게 $R + 10^{-6}$ 이내로 가까워지면, 속도를 유지하는 동안 두 로봇 사이의 거리는 $R - 10^{-6}$보다 작아진다.
• 어떤 로봇이 다른 로봇에게서 $R - 10^{-6}$까지 멀어지면, 속도를 유지하는 동안 두 로봇 사이의 거리는 $R + 10^{-6}$보다 커진다.
• 어떤 한 쌍의 로봇이 시각 $t$에 서로의 무선 범위 안으로 들어오고, (한두 로봇을 공유할 수도 있는) 다른 한 쌍의 로봇이 시각 $t'$에 서로의 무선 범위 밖으로 나간다면, $|t - t'| \ge 10^{-6}$이다.

같은 시각에 같은 위치를 공유하는 로봇이 둘 이상 있을 수도 있으나, 그런 경우에도 로봇은 지정된 속도로 움직인다.

입력의 끝은 세 개의 $0$이 적힌 줄로 표시된다.

각 데이터셋에 대해, 첫 번째 로봇이 시각 $0$에 처음 가지고 있던 관측 데이터를 시각 $T$까지 받게 되는 모든 로봇의 별명을 출력한다. 각 별명을 사전순으로 한 줄에 하나씩, 앞뒤에 불필요한 공백 없이 출력한다. 첫 번째 로봇 자신도 항상 데이터를 가진 것으로 센다. 이 로봇들의 집합은 유일하게 결정된다.