Задача D. Муравьи на сетке ≡

Условие

Пусть имеется некоторая трехмерная область, покрытая регулярной прямоугольной сеткой, между ячейками которой перемещаются муравьи.

Каждый муравей начинает свое движение из некоторой стартовой ячейки и может перемещаться в любом
из шести доступных направлений: вверх, вниз, вправо, влево, вперед и назад.

Известно, что за один шаг по времени каждый муравей может сместиться не более, чем на одну ячейку.

Для известного набора стартовых ячеек требуется определить минимально возможное число шагов,
за которое два муравья могут оказаться в одной ячейке.

Формат входного файла

Входной файл "input.txt" содержит число N, за которым следует набор
из 3 × N целочисленных индексов стартовых ячеек: X_i, Y_i, Z_i.

Формат выходного файла

Выходной файл "output.txt" должен содержать
минимально возможное число шагов,
за которое два муравья встретятся.

Ограничения

 − 10⁶ ≤ (X_i, Y_i, Z_i) ≤ 10⁶, 2 ≤ N ≤ 10⁵

Примеры тестов

5
1 19 37
-9 5 10
4 3 6
9 8 7
17 20 5

6

5
6 49 58
-9 -1 3
2 8 9
-1 2 0
2 8 9

0