Ідеальна піраміда#9526

Ідеальна піраміда

1 секунда

128 мегабайтів

Легка

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

Звісно, справжня піраміда повинна мати чотири сторони, орієнтовані по сторонах світу: дві сторони піраміди повинні йти строго з півночі на південь, а дві — зі сходу на захід. Ідеально збалансована піраміда повинна мати кут нахилу сторін $45°$ , ні більше, ні менше. Для спрощення будівництва піраміда повинна мати цілу висоту і цілі координати центру.

На місці будівництва розташовані $n$ обелісків. $i$ -ий обеліск має координати $(x_{i}, y_{i})$ (x_i, y_i) і висоту $h_{i}$ h_i. Інарос хоче побудувати піраміду так, щоб кожен існуючий обеліск знаходився всередині піраміди. Обеліск вважається всередині піраміди, якщо висота піраміди в точці розташування обеліска більша або дорівнює висоті обеліска.

Оскільки фараон бажає завершити будівництво піраміди за свого життя, він прагне знайти піраміду найменшого розміру, яка вміщає всі обеліски.

Вхідні дані

Перший рядок містить кількість обелісків $n$ ( $1 \leq n \leq 1000$ 1 \le n \le 1000). Кожен з наступних $n$ рядків містить три цілі числа $x_{i}$ x_i, $y_{i}$ y_i, $h_{i}$ h_i ( $- 1 0^{8} \leq x_{i}, y_{i} \leq 1 0^{8}$ -10^8 \le x_i, y_i \le 10^8, $1 \leq h_{i} \leq 1 0^{8}$ 1 \le h_i \le 10^8) - координати $i$ -го обеліска і його висоту.

Вихідні дані

Виведіть три цілі числа $x$ , $y$ , $h$ - координати центру $(x, y)$ оптимальної піраміди і її висоту.

Приклади

Приклад 1

Приклад 2