eolymp
bolt
Try our new interface for solving problems
Problems

Testing Your Geometry Template

Testing Your Geometry Template

Time limit 1 second
Memory limit 256 MiB

You are given n distinct points P_1, P_2, \ldots, P_n 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 \le i < j \le n such that XP_i = XP_j. In other words, S is the set of all points on the x-axis which are equidistant from some two distinct points from P_1, \ldots, P_n.

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.

Input data

The first line contains a single integer n (2 \le n \le 200000) — the number of points.

The i-th of the next n lines contains two integers x_i, y_i (-10^9 \le x_i, y_i \le 10^9, y_i \neq 0) — x and y coordinates of point P_i.

It's guaranteed that S is nonempty and finite in all testcases.

Output data

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 \frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}.

Examples

Input example #1
3
0 1
-2 5
2 5
Output example #1
14.0000000000

Note

In the sample, S = \{(-7, 0), (0, 0), (7, 0)\}.

Note that if S contains a single point, the answer will be 0.

Author Anton Trygub
Source All-Ukrainian Collegiate Programming Contest 2021-2022, II stage