You are given n distinct points P1,P2,…,Pn on the coordinate plane, none of which lie on the x-axis (x-axis is the set of points whose y coordinate is 0).
Let S be the set of all points X on the x-axis such that there exist two integers i,j with 1≤i<j≤n such that XPi=XPj. In other words, S is the set of all points on the x-axis which are equidistant from some two distinct points from P1,…,Pn.
Find the largest distance between any two points in S (not necessarily distinct).
It's guaranteed that in all test cases, S is nonempty and finite.
The first line contains a single integer n (2≤n≤200000) — the number of points.
The i-th of the next n lines contains two integers xi,yi (−109≤xi,yi≤109, yi=0) — x and y coordinates of point Pi.
It's guaranteed that S is nonempty and finite in all testcases.
Output a single number — the largest distance between any two points in S (not necessarily distinct).
Your answer is considered correct if its absolute or relative error does not exceed 10−6.
Formally, let your answer be a, and the jury's answer be b. Your answer is accepted if and only if max(1,∣b∣)∣a−b∣≤10−6.
In the sample, S={(−7,0),(0,0),(7,0)}.
Note that if S contains a single point, the answer will be 0.