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 <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxx=1e5+6;
 
class point {
public:
    double x,y;
    point(double x=0,double y=0):x(x),y(y){}
 
    bool operator < (const point &u)const{
        if(x!=u.x) return x<u.x;
        return y<u.y;
    }   
};
point a[maxx],b[maxx];
 
inline double dis(point a,point b){ return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); }
inline bool cmp(point a,point b){return a.y<b.y;}
double solve(int left,int right){
    if(left+1==right) return dis(a[left],a[right]);
    double xl,xr,xm;
    int mid=(left+right)>>1;
    xl=solve(left,mid);
    xr=solve(mid,right);
    xm=min(xl,xr);
    int k=1;
    for(int i=left;i<=right;i++){
        if(fabs(a[mid].x-a[i].x)<=xm) b[k++]=a[i];
    }
    sort(b+1,b+k,cmp);
    for(int i=1;i<k;i++){
        for(int j=i+1;j<k && (b[j].y-b[i].y<xm);j++){
            xm=min(xm,dis(b[i],b[j]));
        }
    }
    return xm;
}
 
int main() {
    int n;
    double x,y;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lf%lf",&x,&y);
        a[i]=point(x,y);
    }
    sort(a+1,a+1+n);
    double ans=solve(1,n);
    printf("%.6f\n",ans);
    return 0;
}