Optimal Well Location

You are given a list of houses located on a 2D plane. Each house is represented by its coordinates \((x, y)\). The goal is to determine the optimal well location such that the total Manhattan distance from the well to all houses 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| \)

It can be shown that the optimal location is obtained by taking the median of all \(x\)-coordinates and the median of all \(y\)-coordinates independently. In this problem, use the median algorithm where the median is defined as the element at index \(\lfloor n/2 \rfloor\) after sorting the coordinates, even when \(n\) is even.

inputFormat

The first line of input contains an integer \(n\) representing the number of houses.

Each of the next \(n\) lines contains two space-separated integers \(x\) and \(y\), which denote the coordinates of a house.

outputFormat

Output a single line containing two integers: the \(x\)-coordinate and the \(y\)-coordinate of the optimal well location, separated by a space.

3
1 2
3 4
5 6

3 4