18075번 - 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 center.

There are n obelisks at the construction site. The i-th obelisk is a pillar with coordinates (x_i, y_i) and height h_i. 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 — the number of obelisks (1 ≤ n ≤ 1000).

Each of the following n lines contains three integers x_i, y_i, h_i — the coordinates of the i-th obelisk and its height (−10⁸ ≤ x_i, y_i ≤ 10⁸; 1 ≤ h_i ≤ 10⁸).

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