eolymp
bolt
Try our new interface for solving problems
Problems

Busy Bees

Busy Bees

Time limit 2 seconds
Memory limit 256 MiB

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 data

The first line of input contains an integer N, the number of workers (1N10^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 data

Output the coordinates of the required cell. If there are multiple solutions, output any of them.

Examples

Input example #1
3
3 0
4 4
0 2
Output example #1
3 0