Problem: For given n points in metric space, find the distance of the closest points.

Constraints

* 2 ≤ n ≤ 100,000
* -100 ≤ x, y ≤ 100

Input


n
x0 y0
x1 y1
:
xn-1 yn-1


The first integer n is the number of points.

In the following n lines, the coordinate of the i-th point is given by two real numbers xi and yi. Each value is a real number with at most 6 digits after the decimal point.

Output

Print the distance in a line. The output values should be in a decimal fraction with an error less than 0.000001.

Examples

Input

2
0.0 0.0
1.0 0.0


Output

1.000000


Input

3
0.0 0.0
2.0 0.0
1.0 1.0


Output

1.41421356237

Solution (in PYTHON3):

Solution:
import sys
from operator import itemgetter
from math import hypot
from itertools import takewhile, chain, combinations

def ntp(A: list, axis: int = -1):
    length = len(A)
    if length <= 4:
        return min([hypot(x1 - x2, y1 - y2) for (x1, y1), (x2, y2) in combinations(A, 2)])
    
    x_types = len(set(x for x, _ in A))
    axis1 = 2*x_types <= length
    axis2 = not axis1
    mid_idx = length//2
    
    if axis1 != axis:
        A.sort(key = itemgetter(axis1))
    Al, Ar = A[:mid_idx], A[mid_idx:]
    median = A[mid_idx][axis1]
    
    tmd = min(ntp(Al, axis1), ntp(Ar, axis1))
    
    midA = [p for p in chain(takewhile(lambda t: median - tmd < t[axis1], Al[::-1]),\
                             takewhile(lambda t: median + tmd > t[axis1], Ar))]
    midA.sort(key = itemgetter(axis2))
    for i, (x1, y1) in enumerate(midA):
        ub = (x1, y1)[axis2] + tmd
        for x2, y2 in takewhile(lambda t: t[axis2] < ub, midA[i+1:]):
            tmd = min(tmd, hypot(x1 - x2, y1 - y2))
    
    return tmd
n = int(sys.stdin.readline())
Points = [tuple(map(float, sys.stdin.readline().split())) for _ in [0]*n] 
print('{:.10f}'.format(ntp(Points)))