You are given n points in plane. You have to find the point on the plane from which the sum of manhattan distances to all the n points is minimum. If there are multiple such points then print the point having the least manhattan distance from origin.
It is guaranteed that the answer is unique.
Manhattan distance between two points (x1, y1) and (x2, y2), is defined as | x1 - x2 | + | y1 - y2 | where | x | denotes absolute value of x.
First line of input contains an integer N, the number of points.
The next N lines contain two integers xi , yi denoting the coordinates of the ith point.
Print two integers x and y, the coordinates of the desired point, seperated by a space.
Update : The desired point need not be among the N given points
1 ≤ N ≤ 105
0 ≤ | xi | , | yi | ≤ 109
(0,2) is the only valid point. Sum of Manhattan distances is (|-1-0| + |2-2|) + (|0-0| + |2-2|) + (|1-0| + |2-2|) = 2