Задача #3293

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

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

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

Входные данные:
В первой строке записано одно целое число N — количество попаданий ($1\le N⩽1000000$). В следующих N строках заданы тройки целых чисел x y t — координаты клетки и время попадания ($1\le x⩽10000$, $1\le y⩽10000$, $0\le t\le {10}^6$).

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

Типовой пример организации входных данных:
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.