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:
# CGL_5_A: Point Set - Closest Pair

from operator import itemgetter
from math import sqrt


def closest_distance(ps):
    def split(i, j):
        if j - i < 2:
            return float('INF')
        mid = (i + j) // 2
        d = min(split(i, mid), split(mid, j))
        lv, rv = ps[mid][0]-d, ps[mid][0]+d
        return merge(sorted([p for p in ps[i:j] if lv <= p[0] <= rv],
                            key=itemgetter(1)), d)

    def merge(_ps, d):
        n = len(_ps)
        for i in range(n-1):
            for j in range(i+1, n):
                if d < _ps[j][1] - _ps[i][1]:
                    break
                d = min(d, distance(_ps[i], _ps[j]))

        return d

    ps.sort(key=itemgetter(0, 1))
    return split(0, len(ps))


def dot(p0, p1):
    x0, y0 = p0
    x1, y1 = p1
    return x0*x1 + y0*y1


def distance(p0, p1):
    x0, y0 = p0
    x1, y1 = p1
    return sqrt((x1-x0)**2 + (y1-y0)**2)


def run():
    n = int(input())
    ps = []

    for _ in range(n):
        x, y = [float(i) for i in input().split()]
        ps.append((x, y))

    print("{:.10f}".format(closest_distance(ps)))


if __name__ == '__main__':
    run()