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 r(i,n) for(int i=0;i<n;i++)
using namespace std;
   
typedef pair<double,double> P;
typedef pair<P,double> P2;
   
P rot(P p, double a){
  a=a*M_PI/180.0;
  return P(p.first*cos(a)+p.second*(-sin(a)),
  p.first*sin(a)+p.second*cos(a));
}
   
double abss(P a,P b){
  return sqrt((a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second));
}
   
double x,y,r;int tt;
vector<P>v;
int main(){
   
  int n;
  cin>>n;
   
    double ans=1e13;
       
    v.clear();
     
    r(i,n){
      cin>>x>>y;
      v.push_back(P(x,y));
    }
   
    r(i,1){
      sort(v.begin(),v.end());
      r(j,n){
        for(int k=j+1,c=0;k<n;k++,c++){
          if(c>1000)break;
          ans=min(ans,abss(v[k],v[j]));
        }
      }
      r(j,n)v[i]=rot(v[i],0.5);
    }
   
    printf("%.11f\n",ans);
       
}