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>
#define nmax 1000010
#define f(c,a,b) for(int c=a; c<=b; c++)
#define inf 1e24

using namespace std;
typedef double db;
struct P{
    db x, y;
    P(){}
    P(db x, db y) : x(x) , y(y) {}
    P operator - (P a){ return P(x-a.x, y-a.y); }
    db clen(){ return sqrt(x*x+y*y); }
};
P p[nmax], t[nmax];
int n;
bool c_x(P& a, P& b) { return a.x < b.x; }
bool c_y(P& a, P& b) { return a.y < b.y; }

db closestP(int l, int r){
    db ta = inf;
    if(r-l<=4){
        f(i,l,r) f(j,i+1,r) ta = min(ta, (p[i]-p[j]).clen() );
        sort(p+l, p+r+1, c_y);
    }else{
        int mid = (l+r)>>1;
        db mx = p[mid].x, d;
        ta = d = min( closestP(l,mid), closestP(mid+1,r) );
        merge(p+l, p+mid+1, p+mid+1, p+r+1, t, c_y);
        copy(t, t+r-l+1, p+l);
        int jsz=0;
        f(i,l,r) if( abs(p[i].x-mx) < d ) {
                for (int j=jsz; j>=1 && p[i].y-t[j].y<d; j--) ta = min(ta, (t[j]-p[i]).clen() );   
                t[++jsz] = p[i];
        }
    }
    return ta;
}

int main(){
    //freopen("owo.in","r",stdin);
    cin >> n;
    f(i,1,n) scanf("%lf%lf", &p[i].x, &p[i].y);
    sort(p+1, p+n+1, c_x);
    printf("%.11lf\n", closestP(1, n));
    return 0;
}