Обработка данных с сортировкой

(Д. Бахтиев) Во время матча в расширенной версии игры «Морской бой» велась автоматическая фиксация попаданий по игровому полю. Каждое попадание фиксируется по координатам клетки игрового поля (целые положительные числа x и y) и времени попадания — целому числу t (в секундах от начала матча).

Игровое поле — прямоугольное. Координаты попаданий (x, y) указываются в формате: x — номер строки (считая сверху вниз, от 1 с шагом 1), y — номер столбца (слева направо, от 1 с шагом 1). Некоторые клетки могли быть поражены несколько раз.

Требуется определить такую клетку, в которую было произведено не менее двух попаданий, и среди них — найти ту, в которой минимальный интервал времени между любыми двумя её попаданиями — наименьший. В ответе нужно вывести сумму координаты этой клетки (x + y), а также этот минимальный интервал в секундах. Если таких клеток несколько, выберите среди них клетку с наименьшим номером строки, а если таких тоже несколько — с наименьшим номером столбца.

Входные данные: В первой строке записано одно целое число N — количество попаданий (1 ≤ N ≤ 1 000 000). В следующих N строках заданы тройки целых чисел x y t — координаты клетки и время попадания (1 ≤ x ≤ 10 000, 1 ≤ y ≤ 10 000, 0 ≤ t ≤ 10⁶).

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

Типовой пример организации входных данных: 7 2 3 10 1 1 3 2 3 15 3 2 20 1 1 10 2 3 17 1 1 6 Для приведённого примера более одного попаданий было в клетки с координатами (2, 3) и (1,1). Минимальный интервал между попаданиями, равный двум секундам, был у клетки с координатами (2, 3). Ответ: 5 2.