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>
using namespace std;
typedef double db;
const db inf =1e9;
const int N=1e5+10;
struct Point{
    db x,y;
    void input(){scanf("%lf%lf",&x,&y);}
    db dis(Point p){return sqrt((p.x-x)*(p.x-x)+(p.y-y)*(p.y-y));}
}A[N];
bool cmp2(Point a,Point b){return a.y<b.y;}
db Closest(int l,int r){
    if(l==r)return inf;
    if(r==l+1)return A[l].dis(A[r]);
    int mid=(l+r)/2;
    db ans=min(Closest(l,mid-1),Closest(mid+1,r));
    vector<Point> V;V.push_back(A[mid]);
    int now=mid-1;while(now>=l&&A[mid].x-A[now].x<=ans)V.push_back(A[now]),--now;
    now=mid+1;while(now<=r&&A[now].x-A[mid].x<=ans)V.push_back(A[now]),++now;
    sort(V.begin(),V.end(),cmp2);
    now=0;
    for(int i=0;i<V.size();++i){
        while(now<V.size()&&V[now].y-V[i].y<=ans)++now;
        for(int j=i;j<now;++j)for(int k=j+1;k<now;++k)ans=min(ans,V[j].dis(V[k]));
    }
    return ans;
}
bool cmp(Point a,Point b){return a.x<b.x;}
int main(){
    int n;cin>>n;
    for(int i=1;i<=n;++i)A[i].input();
    sort(A+1,A+1+n,cmp);
    printf("%.10lf\n",Closest(1,n));
}