Go Go Горелиане
Горелиане путешествуют по космосу, используя варп-ссылки. Путешествие через варп-ссылку происходит мгновенно, но по соображениям безопасности каждый может перемещаться только раз в 10 часов. Кроме того, стоимость создания варп-ссылки увеличивается прямо пропорционально линейному расстоянию между её конечными точками.
Горелиане, будучи доминирующей силой в известной вселенной, часто скучают и поэтому завоёвывают новые регионы космоса следующим образом:
Начальная сила вторжения находит подходящую планету и завоёвывает её, создавая Региональное Горелианское Галактическое Правительство, далее именуемое как РГГП, которое будет управлять всеми горелианскими делами в этом регионе космоса.
Когда следующая планета завоёвана, между новой планетой и планетой РГГП строится одна варп-ссылка. Планеты, соединённые варп-ссылками таким образом, считаются частью Региональной Горелианской Планетарной Сети, то есть РГПС.
По мере завоевания дополнительных планет, каждая новая планета соединяется одной варп-ссылкой с ближайшей планетой, уже находящейся в РГПС, таким образом, чтобы минимизировать стоимость подключения новых планет к сети. Если две или более планет находятся на одинаковом расстоянии от новой планеты, новая планета соединяется с той из них, которая была завоёвана первой.
Однако это вызывает проблему. Поскольку планеты завоёвываются более-менее случайным образом, через некоторое время РГГП вероятно не будет находиться в идеальном месте. Некоторым горелианам, нуждающимся в консультации с РГГП, может потребоваться сделать всего один или два варпа, но другим может потребоваться десятки — что очень неудобно, учитывая 10-часовой период ожидания между варпами.
Поэтому раз в горелианский год РГГП анализирует РГПС и перемещается в оптимальное место. Оптимальное место определяется как планета, которая минимизирует максимальное количество варпов, необходимых для достижения РГГП с любой планеты в РГПС. Как оказывается, всегда существует ровно одна или две такие планеты. Когда их две, они всегда непосредственно связаны варп-ссылкой, и РГГП делится поровну между двумя планетами.
Ваша задача — написать программу, которая находит оптимальные планеты для РГГП. Для целей этой задачи регион космоса, завоёванный горелианами, определяется как куб, который варьируется от (0, 0, 0) до (1000, 1000, 1000).
Входные данные
Входные данные состоят из набора сценариев, где горелиане завоёвывают регион космоса. Каждый сценарий независим. Первая строка сценария — это целое число N, которое указывает общее количество планет, завоёванных горелианами. Следующие N строк входных данных указывают, в порядке завоевания, ID и координаты завоёванных планет, которые добавляются в РГПС, в формате ID X Y Z. ID — это целое число от 1 до 1000. X, Y и Z — целые числа от 0 до 1000. Одно пробел разделяет числа. Значение N = 0 обозначает конец ввода.
Выходные данные
Для каждого сценария ввода выведите ID оптимальной планеты или планет, куда должно переместиться РГГП. Для одной планеты просто выведите ID планеты. Для двух планет выведите ID планет, сначала меньший ID, разделённые одним пробелом.