1/8 ICPC Azerbaijan Qualification Preparation

Ideal Pyramid

Every pharaoh cares about his legacy. Reigning pharaoh Inaros the Great wants to be remembered for a long time. He is going to build the largest pyramid the humankind has ever seen.

Of course, the proper pyramid should have four sides at the bottom, oriented to the cardinal directions - two sides of the pyramid should go exactly from north to south, and two sides should go from east to west. The perfectly balanced pyramid should have the slope angle of the side equal to 45◦, no more, no less. To simplify construction, the pyramid should have integer height and integer coordinates of the centre.

There are n obelisks at the construction site. The i-th obelisk is a pillar with coordinates (xi, yi) and height hi. Inaros wants to build a pyramid so that each existing obelisk would be inside the pyramid. The obelisk is inside the pyramid if the height of the pyramid at the obelisk position is greater than or equal to the height of the obelisk.

Since the pharaoh wants to finish the construction of the pyramid during his life, he wants to find the smallest possible pyramid that contains all of the obelisks.


The first line contains a single integer n (1n1000) - the number of obelisks. Each of the following n lines contains three integers xi, yi, hi (-108xi, yi108, 1hi108) - the coordinates of the i-th obelisk and its height.


Output three integers x, y, h - the coordinates of the centre (x, y) of the optimal pyramid and its height.

Time limit 1 second
Memory limit 128 MiB
Input example #1
0 0 5
Output example #1
0 0 5
Input example #2
3 3 3
6 6 2
Output example #2
4 4 4
Source 2019 ACM NEERC, Northern Subregion, October 26, Problem I