АВТ ВоГУ - Задача 1604. Метро

Метро города Нью-Славец состоит из n станций. Расположение каждой станции можно задать координатами в декартовой системе координат: x_i, y_i, z_i. При создании подземки для помощи привлекли учёных с дружественной нам звезды. Инопланетяне использовали неизвестные технологии и создали очень сложную систему дорог. Чтобы добраться от станции i до станции j, требуется $\text{[math]}$ миллисекунд. Учёных со всей Земли особенно удивляет, что $\text{[math]}$ может быть больше нуля и $\text{[math]}$ может быть не равно $\text{[math]}$ .

Нью-Славцы пользуются метро уже несколько лет, но так и не поняли, сколько времени добираться между станциями. Известная рок-группа «Високосная секунда» решила написать новую песню про две самые удалённые станции метро. Помогите группе порадовать слушателей новой песней, найдите номера двух самых удалённых станций.

Стоит заметить, что в метро нельзя делать пересадки, и группу интересуют две различные станции.

Входные данные

В первой строке задано натуральное число n — количество станций в Нью-Славском метро (2 ≤ n ≤ 1 000 000). Далее на n различных строках записаны по три числа — координаты каждой станции x_i, y_i, z_i. Координаты по модулю не превосходят 10⁵.

Выходные данные

В первой строке выведите время в миллисекундах между двумя наиболее удалёнными станциями, то есть максимальное $\text{[math]}$ (x ≠ y). Во второй строке выведите два различных числа x и y — номера двух наиболее удалённых станций. Станции нумеруются с единицы в порядке задания их во входном файле. Если ответов несколько — выведите любой.

Примеры

Входные данные

2
1 2 3
3 1 2

Выходные данные

4
2 1

Входные данные

Выходные данные

4
1 5

Дистанционный практикум по программированию

1604. Метро