Optimal Meeting Point

You are given an integer n representing the number of friends and n pairs of coordinates in the 2D plane. Each coordinate represents a friend's location. Your task is to determine the optimal meeting point that minimizes the total Manhattan distance traveled by all friends. In other words, if the meeting point is \( (m_x, m_y) \), you need to minimize
\( \sum_{i=1}^{n} (|x_i-m_x| + |y_i-m_y|) \).

This optimal point is achieved when \( m_x \) is the median of all x-coordinates and \( m_y \) is the median of all y-coordinates. Note that when \( n \) is even, this definition selects the \( \lceil \frac{n}{2} \rceil \)-th smallest coordinate.

inputFormat

The first line of input contains a single integer n (1 ≤ n ≤ 10⁵), the number of friends. The next n lines each contain two space-separated integers representing the x and y coordinates of a friend's location. The coordinates are within the range \( [-10^9, 10^9] \).

outputFormat

Output a single line with two space-separated integers representing the optimal meeting point's coordinates \( (m_x, m_y) \).

1
1 2

1 2