eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Идеальная пирамида

Идеальная пирамида

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Каждый фараон заботится о своем наследии. Правящий фараон Инарос Великий хочет, чтобы его запомнили надолго. Он собирается построить самую большую пирамиду, которую когда-либо видело человечество.

Конечно, правильная пирамида должна иметь четыре стороны внизу, ориентированные по сторонам света - две стороны пирамиды должны идти точно с севера на юг, а две стороны должны идти с востока на запад. Идеально сбалансированная пирамида должна иметь угол наклона стороны 45°, не больше и не меньше. Для упрощения построения пирамида должна иметь целую высоту и целые координаты центра.

На стройке стоят n обелисков. i - ый обелиск представляет собой столб с координатами (x[i], y[i]) и высотой h[i]. Инарос хочет построить пирамиду, чтобы каждый существующий обелиск находился внутри пирамиды. Обелиск находится внутри пирамиды, если высота пирамиды в месте расположения обелиска больше или равна высоте обелиска.

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

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

Первая строка содержит количество обелисков n (1n1000). Каждая из следующих n строк содержит три целых числа x[i], y[i], h[i] (-10^8x[i], y[i]10^8, 1h[i]10^8) - координаты i-го обелиска и его высоту.

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

Выведите три целых числа x, y, h - координаты центра (x, y) оптимальной пирамиды и ее высота.

Пример

Входные данные #1
1
0 0 5
Выходные данные #1
0 0 5
Входные данные #2
2
3 3 3
6 6 2
Выходные данные #2
4 4 4
Источник 2019 ACM NEERC, Северный регион, Октябрь 26, Задача I