Best Meeting Point

You are given a set of robots located at various points on a 2D grid. The task is to determine the best meeting point (x, y) such that the sum of the Manhattan distances from each robot to this meeting point is minimized. The Manhattan distance between two points \( (x_1, y_1) \) and \( (x_2, y_2) \) is given by \( |x_1-x_2| + |y_1-y_2| \).

The optimal strategy to minimize the total Manhattan distance is to choose the median of the x-coordinates and the median of the y-coordinates. In the case where the number of robots, \( n \), is even, choose the lower median (i.e. the element at index \( \frac{n}{2}-1 \)) after sorting the coordinates.

inputFormat

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

outputFormat

Output the best meeting point as two space-separated integers \( x \) and \( y \) on a single line. The output should be written to standard output.

1
0 0

0 0