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:
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
using namespace std;

const double EPS = 1e-10;
double add(double a, double b) {
    if(abs(a+b) < EPS*(abs(a)+abs(b))) return 0;
    return a+b;
}
struct Vector {
    double x, y;
    Vector() {}
    Vector(double x, double y):x(x), y(y) {}
    Vector operator+(Vector v) {return Vector(add(x, v.x), add(y, v.y));}
    Vector operator-(Vector v) {return Vector(add(x, -v.x), add(y, -v.y));}
    Vector operator*(double d) {return Vector(x*d, y*d);}
    Vector operator/(double d) {return Vector(x/d, y/d);}
    double dot(Vector v) {return add(x*v.x, y*v.y);}
    double cross(Vector v) {return add(x*v.y, -y*v.x);}
};
istream &operator>>(istream &is, Vector &v) {return is >> v.x >> v.y;}
ostream &operator<<(ostream &os, const Vector &v) {return os << v.x << ' ' << v.y;}
double sqdist(Vector &v, const Vector &u) {return (v-u).dot(v-u);}
//線分v2-v1上にあるか
bool on_seg(Vector &v1,Vector &v2, const Vector &p) {
    return (v1-p).cross(v2-p) == 0 && (v1-p).dot(v2-p) <= 0;
}
//v1-v2とu1-u2の交点
Vector intersection(Vector &v1,Vector &v2,Vector &u1,Vector &u2) {
    assert((v1-v2).cross(u1-u2)); //2直線が平行だとだめ
    return v1 + (v2-v1)*((u2-u1).cross(u1-v1)/(u2-u1).cross(v2-v1));
}
//p2-p1へのQの投影
Vector projection(Vector &p1,Vector &p2,Vector &Q) {
    return p1+(p2-p1)*(Q-p1).dot(p2-p1)/sqdist(p1, p2);
}
//p1-p2を軸としたQの線対称移動
Vector reflection(Vector &p1,Vector &p2,Vector &Q) {
    return projection(p1, p2, Q)*2-Q;
}
bool cmp_x(const Vector &v, const Vector &u) {
    if(v.x != u.x) return v.x < u.x;
    return v.y < u.y;
}
bool cmp_y(const Vector &v, const Vector &u) {
    if(v.y != u.y) return v.y < u.y;
    return v.x < u.x;
}
//頂点数nの頂点集合vv
vector<Vector> convex_hull(vector<Vector> &vv, int n) {
    sort(vv.begin(), vv.end(), cmp_x);
    int k = 0;
    vector<Vector> res(n*2);
    for(int i = 0; i < n; i++) {
        while(k > 1 && (res[k-1]-res[k-2]).cross(vv[i]-res[k-1]) <= 0) k--;
        res[k++] = vv[i];
    }
    for(int i = n-2, t = k; i >= 0; i--) {
        while(k > t && (res[k-1]-res[k-2]).cross(vv[i]-res[k-1]) <= 0) k--;
        res[k++] = vv[i];
    }
    res.resize(k-1);
    return res;
}
//点と線の距離
double distpl(Vector &p0, Vector &p1, Vector &Q) {
    Vector pp = projection(p0, p1, Q);
    return sqrt(sqdist(pp, Q));
}
//線分と線分の距離
double distss(Vector &p0, Vector &p1, Vector &p2, Vector &p3) {
    if((p0-p1).cross(p2-p3) != 0) {
        Vector p = intersection(p0, p1, p2, p3);
        if(on_seg(p0, p1, p) and on_seg(p2, p3, p)) {
            return 0.0;
        }
    }
    double res = min({sqdist(p0, p2), sqdist(p0, p3), sqdist(p1, p2), sqdist(p1, p3)});
    Vector pp0, pp1, pp2, pp3;
    pp2 = projection(p0, p1, p2);
    pp3 = projection(p0, p1, p3);
    pp0 = projection(p2, p3, p0);
    pp1 = projection(p2, p3, p1);
    if(on_seg(p0, p1, pp2)) res = min(res, sqdist(pp2, p2));
    if(on_seg(p0, p1, pp3)) res = min(res, sqdist(pp3, p3));
    if(on_seg(p2, p3, pp0)) res = min(res, sqdist(pp0, p0));
    if(on_seg(p2, p3, pp1)) res = min(res, sqdist(pp1, p1));
    res = sqrt(res);
    return res;
}

double closestPair(vector<Vector> &vv, int l, int r) {
    if(r-l <= 1) return 1e9;
    int m = (l+r)/2;
    double x = vv[m].x;
    double d = min(closestPair(vv, l, m), closestPair(vv, m, r));
    inplace_merge(vv.begin()+l, vv.begin()+m, vv.begin()+r, cmp_y);
    vector<Vector> b;
    for(int i = l; i < r; i++) {
        if(abs(x-vv[i].x) >= d) continue;
        for(int j = b.size()-1; j >= 0; j--) {
            if((vv[i]-b[j]).y >= d) break;
            d = min(d, sqrt(sqdist(vv[i], b[j])));
        }
        b.push_back(vv[i]);
    }
    return d;
}

double closestPair(vector<Vector> &vv) {
    sort(vv.begin(), vv.end(), cmp_x);
    return closestPair(vv, 0, vv.size());
}

signed main() {
    cout << fixed << setprecision(13);
    int n;
    cin >> n;
    vector<Vector> X(n);
    rep(i, n) {
        cin >> X[i];
    }

    cout << closestPair(X) << endl;
}