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 f first
#define s second
#define mp make_pair
#define pi M_PI
#define inf 1<<30
#define eps (1e-11)
#define MAX 100010
#define equals(a,b) (fabs((a)-(b))<eps)
using namespace std;

class Point{
public:
  double x,y;
  Point(double x=0,double y=0):x(x),y(y){}

  Point operator+(Point p){ return Point(x+p.x,y+p.y);}
  Point operator-(Point p){ return Point(x-p.x,y-p.y);}
  Point operator*(double k){ return Point(x*k,y*k);}
  Point operator/(double k){ return Point(x/k,y/k);}
  bool operator<(Point p)const{ return (x!=p.x ? x<p.x : y<p.y);}
  bool operator==(Point p)const{ return fabs(x-p.x)<eps && fabs(y-p.y)<eps;}

  double abs(){ return sqrt(norm());}
  double norm(){ return (x*x+y*y);}
};
typedef Point Vector;
typedef vector<Point> Polygon;

Point A[MAX];
int n;

bool compare_y(const Point &a,const Point &b){
  return a.y<b.y;
}

double closest_pair(Point *a,int n){
  if(n<=1)return inf;
  int m=n/2;
  double x=a[m].x;
  double d=min(closest_pair(a,m),closest_pair(a+m,n-m));
  inplace_merge(a,a+m,a+n,compare_y);

  vector<Point> b;
  for(int i=0;i<n;i++){
    if(fabs(a[i].x-x)>=d)continue;

    for(int j=0;j<b.size();j++){
      double dx=a[i].x-b[b.size()-j-1].x;
      double dy=a[i].y-b[b.size()-j-1].y;
      if(dy>=d)break;
      d=min(d,sqrt(dx*dx+dy*dy));
    }
    b.push_back(a[i]);
  }
  return d;
}

int main()
{
  cin>>n;
  for(int i=0;i<n;i++)cin>>A[i].x>>A[i].y;

  sort(A,A+n);

  printf("%.10f\n",closest_pair(A,n));

  return 0;
}