Busy Bees
Description
There is an infinite beehive consisting of hexagonal cells. Some cells contain workers which deliver honey to the queen. Each cell can contain any number of bees at any moment in time. Workers can move between cells that have a common edge, but the queen cannot move. The distance between two cells is defined as the minimum number of moves required for a worker to travel between them. The workers are very busy and they want to spend as little time as possible traveling to the queen.
You are given the coordinates of $N$ distinct cells that contain workers. The coordinate system is illustrated below:
Find the cell where the queen should be placed so that the sum of distances between her cell and all the cells containing workers is minimized.
The first line of input contains an integer $N$, the number of workers ($1 \le N \le 10^5$). The next $N$ lines each contain two integers, the coordinates of the worker cells. Each coordinate does not exceed $10^9$ in absolute value. It is guaranteed that all cells are distinct.
Output the coordinates of the required cell. If there are multiple solutions, output any of them.
Input
The first line of input contains an integer $N$, the number of workers ($1 \le N \le 10^5$). The next $N$ lines each contain two integers, the coordinates of the worker cells. Each coordinate does not exceed $10^9$ in absolute value. It is guaranteed that all cells are distinct.
Output
Output the coordinates of the required cell. If there are multiple solutions, output any of them.
3
3 0
4 4
0 2
4
0 -2
0 0
0 2
2 0
2 2
0 0