Busy Bees
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 of time. Workers can move between cells that have a common edge, and the queen can not move. The distance between two cells is the minimum number of moves required for a worker to travel between them. Workers are very busy and they want to spend minimal possible time to travel to the queen.
You are given coordinates of N distinct cells which 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 which contain workers is minimal possible.
Input
The first line of input contains an integer N, the number of workers (1 ≤ N ≤ 10^5). Next N lines contain two integers each: coordinates of workers cells. Each of the coordinates does not exceed 10^9 by 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.