고고 고렐리안

고렐리안(Gorelian)은 워프 링크(warp link)를 이용해 우주를 이동한다. 워프 링크를 통한 이동은 순간적으로 이루어지지만, 안전상의 이유로 한 개체는 10시간에 한 번만 워프할 수 있다. 또한 워프 링크를 만드는 비용은 링크 양 끝점 사이의 직선 거리에 정비례해 증가한다.

알려진 우주에서 지배적인 세력인 고렐리안은 자주 지루함을 느껴, 다음과 같은 방식으로 새로운 우주 영역을 정복하곤 한다.

1. 최초의 침공 부대가 적당한 행성을 찾아 정복하고, 그 영역의 모든 고렐리안 사안을 관장하는 지역 고렐리안 은하 정부(Regional Gorelian Galactic Government, 이하 RGGG)를 세운다.

2. 다음 행성이 정복되면, 새 행성과 RGGG 행성 사이에 워프 링크 하나를 만든다. 이렇게 워프 링크로 연결된 행성들의 집합을 지역 고렐리안 행성 네트워크(Regional Gorelian Planetary Network, 이하 RGPN)라고 부른다.

3. 이후 행성이 추가로 정복될 때마다, 새 행성은 이미 RGPN에 속한 행성 중 가장 가까운 행성 하나와 워프 링크로 연결된다. 이렇게 하여 새 행성을 네트워크에 붙이는 비용을 최소로 유지한다. 만약 새 행성으로부터의 거리가 같은 행성이 둘 이상이면, 그중 가장 먼저 정복된 행성에 연결한다.

그런데 이 방식에는 문제가 있다. 행성이 다소 무작위한 순서로 정복되기 때문에, 시간이 지나면 RGGG가 이상적인 위치에 있지 않을 가능성이 크다. RGGG에 자문해야 하는 어떤 고렐리안은 워프를 한두 번만 하면 되지만, 다른 고렐리안은 수십 번을 해야 할 수도 있다. 워프 사이에 10시간을 기다려야 한다는 점을 고려하면 매우 불편한 일이다.

그래서 고렐리안의 1년에 한 번, RGGG는 RGPN을 분석해 최적의 위치로 이전한다. 최적의 위치란, RGPN의 임의의 행성에서 RGGG에 도달하는 데 필요한 워프 횟수의 최댓값을 최소로 만드는 행성이다. 그런 행성은 항상 정확히 한 개 또는 두 개 존재한다. 두 개일 때 두 행성은 항상 워프 링크로 직접 인접해 있으며, RGGG는 자신을 두 행성에 균등하게 나눈다.

여러분의 임무는 RGGG가 이전할 최적의 행성을 찾는 프로그램을 작성하는 것이다. 이 문제에서 고렐리안이 정복하는 우주 영역은 $(0, 0, 0)$부터 $(1000, 1000, 1000)$까지의 정육면체이다.

입력은 여러 개의 시나리오로 이루어지며, 각 시나리오는 서로 독립적이고 고렐리안이 한 우주 영역을 정복하는 상황을 나타낸다. 각 시나리오의 첫 줄에는 정복된 행성의 총 개수를 나타내는 정수 $N$이 주어진다. 이어지는 $N$개의 줄에는 RGPN에 추가된 행성들이 정복된 순서대로 ID X Y Z 형식으로 주어진다. ID는 1 이상 1000 이하의 정수이고, $X$, $Y$, $Z$는 0 이상 1000 이하의 정수이다. 한 줄의 숫자들은 공백 하나로 구분된다. $N = 0$인 줄은 입력의 끝을 나타낸다.

각 시나리오마다 RGGG가 이전해야 할 최적의 행성 ID를 출력한다. 행성이 하나이면 그 행성의 ID를 출력하고, 두 개이면 두 ID를 작은 것부터 공백 하나로 구분해 출력한다.