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, розділені одним пробілом.