Placing a Basketball Hoop

In a grid country, there is a village at every integer coordinate. The distance between two villages is the shortest distance when moving along the roads, also known as Manhattan distance. From (x1, y1) to (x2, y2), this distance is |x2 - x1| + |y2 - y1|.

You are given the locations of n villages where people like basketball, and the number of such people in each village. The country wants to place exactly one basketball hoop for all of them.

The hoop must be placed at a village with integer coordinates, but that village does not have to be one of the input villages. For every basketball-loving village, compute (distance from that village to the hoop) × (number of people in that village). Find a hoop location that minimizes the sum of these values.

The first line contains n, the number of villages where people like basketball. Each of the next n lines contains xi yi pi, describing one village: its coordinates are (xi, yi), and pi people there like basketball.

No two villages have the same location.

Print the coordinates x y of the village where the hoop should be placed. If there are multiple optimal locations, choose the one with the smallest x coordinate; if there is still more than one, choose the one with the smallest y coordinate.

• 1 ≤ n ≤ 100,000
• -1,000,000 ≤ xi, yi ≤ 1,000,000
• 1 ≤ pi ≤ 1,000