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 CPP):

Solution:
#include <bits/stdc++.h>
#include <unistd.h>
using namespace std;

const double eps = 1e-10;

int dcmp(double x) {
        if(fabs(x) < eps) return 0;
        return x < 0 ? -1 : 1;
}

bool same(double a, double b) {return dcmp(a - b) == 0;}
#define Vector P
struct P {
        double x, y;
        P(double x = 0, double y = 0): x(x), y(y) {}
        P operator + (P b) {return P(x + b.x, y + b.y);}
        P operator - (P b) {return P(x - b.x, y - b.y);}
        P operator * (double b) {return P(x * b, y * b);}
        P operator / (double b) {return P(x / b, y / b);}
        double operator * (P b) {return x * b.x + y * b.y;} // Dot
        double operator ^ (P b) {return x * b.y - y * b.x;} // Cross
        double abs() {return hypot(x, y);}
        P unit() {return *this / abs();}
        P spin(double o) {
                double c = cos(o), s = sin(o);
                return P(c * x - s * y, s * x + c * y);
        }
};

struct Line {
        //ax + by + c = 0
        double a, b, c, theta;
        P pa, pb;
        Line(): a(0), b(0), c(0), theta(0), pa(), pb() {}
        Line(P pa, P pb): a(pa.y - pb.y), b(pb.x - pa.x), c(pa ^ pb), theta(atan2(-a, b)), pa(pa), pb(pb) {}
                P projection(P p) {return pa + (pb - pa).unit() * ((pb - pa) * (p - pa) / (pb - pa).abs());}
                P reflection(P p) {return p + (projection(p) - p) * 2;}
        double get_ratio(P p) {return (p - pa) * (pb - pa) / ((pb - pa).abs() * (pb - pa).abs());}
        P dis(P p) {return ((pb - pa) ^ (p - pa)) / (pb - pa).abs();} // directed distance
};

struct Circle {
        P c;
        double r;
        Circle(P c, double r = 0): c(c), r(r) {}
};
double dis(P a, P b) {return (a - b).abs();}
vector<P> p;
double closest_pair(int l, int r) {
    // p should be sorted increasingly according to the x-coordinates.
    if (l == r) return 1e9;
    if (r - l == 1) return dis(p[l], p[r]);
    int m = (l + r) >> 1;
    double d = min(closest_pair(l, m), closest_pair(m + 1, r));
    vector<int> vec;
    for (int i = m; i >= l && fabs(p[m].x - p[i].x) < d; --i) vec.push_back(i);
    for (int i = m + 1; i <= r && fabs(p[m].x - p[i].x) < d; ++i) vec.push_back(i);
    sort(vec.begin(), vec.end(), [&](int a, int b) { return p[a].y < p[b].y; });
    for (int i = 0; i < vec.size(); ++i) {
        for (int j = i + 1; j < vec.size() && fabs(p[vec[j]].y - p[vec[i]].y) < d; ++j) {
            d = min(d, dis(p[vec[i]], p[vec[j]]));
        }
    }
    return d;
}
int main() {
        ios_base::sync_with_stdio(false); cin.tie(0);
        int n; cin >> n;
        for(int i = 0; i < n; i++) {
                P ps; cin >> ps.x >> ps.y;
                p.push_back(ps);
        }
                sort(p.begin(), p.end(), [&](P a, P b) {return same(a.x, b.x) ? a.y < b.y : a.x < b.x;});                   double ans = closest_pair(0, n - 1);
        cout << fixed << setprecision(12) << ans << '\n';
        return 0;
}