Squirrel Meeting House

There are a group of little squirrels living on a prairie, each with its own home represented as a point \((x,y)\). Over time, they decide to gather for a party, but they are confused about whose house would be the most ideal meeting place. The distance between any two homes is defined using the Chebyshev distance, i.e. the distance between \((x,y)\) and any of its 8 neighboring points (\((x-1,y)\), \((x+1,y)\), \((x,y-1)\), \((x,y+1)\), \((x-1,y+1)\), \((x-1,y-1)\), \((x+1,y+1)\), \((x+1,y-1)\)) is \(1\).

Your task is to select one of the existing squirrel homes as the meeting point such that the maximum distance from that home to all other homes is minimized. In other words, for each candidate home \((x_i,y_i)\), compute \(d_i = \max_{j}\ {\rm Chebyshev\_distance}((x_i,y_i), (x_j,y_j))\), and choose the home with the minimum \(d_i\). If there are multiple such homes, choose the one with the smallest \(x\)-coordinate; if still tied, choose the one with the smallest \(y\)-coordinate.

The Chebyshev distance between two points \((x_1,y_1)\) and \((x_2,y_2)\) is defined as:

[ \text{distance} = \max(|x_1-x_2|,,|y_1-y_2|) ]

inputFormat

The first line contains an integer \(n\) representing the number of squirrels (and hence, homes). Each of the next \(n\) lines contains two integers \(x\) and \(y\) representing the coordinates of a squirrel's home.

outputFormat

Output three integers: the \(x\) and \(y\) coordinates of the chosen meeting house, followed by the minimized maximum Chebyshev distance. The three numbers should be separated by a single space.

sample

3
0 0
0 2
2 0

0 0 2