Manhattan Median Building

You are given a set of building coordinates on a 2D grid. Your task is to choose a building such that the sum of the Manhattan distances from this building to all the other buildings is minimized.

The Manhattan distance between two points \( (x_1, y_1) \) and \( (x_2, y_2) \) is defined as \( |x_1 - x_2| + |y_1 - y_2| \). It is known that for Manhattan distances the median minimizes the total distance. If there are several optimal buildings, select the one with the smallest x-coordinate; if there is still a tie, choose the one with the smallest y-coordinate.

Formally, given a list of \( n \) buildings with coordinates \( (x_i, y_i) \) for \( i=1,2,\ldots,n \), find the building \( (x, y) \) such that the total Manhattan distance \( \sum_{i=1}^{n} \left(|x - x_i| + |y - y_i|\right) \) is minimized. In case of multiple answers, pick the one with the smallest \( x \), and if there is a tie, the smallest \( y \).

inputFormat

The input is read from standard input (stdin). The first line contains an integer ( n ) ( (1 \leq n \leq 10^6) ), the number of buildings. Each of the following ( n ) lines contains two space-separated integers ( x ) and ( y ) (( -10^6 \leq x, y \leq 10^6 )), representing the coordinates of a building.

outputFormat

Print two integers separated by a space to standard output (stdout) representing the ( x ) and ( y ) coordinates of the building that minimizes the total Manhattan distance to all other buildings. In case of multiple solutions, print the one with the smallest ( x ), and then the smallest ( y ).## sample

1
1 2

1 2