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;

struct point{
  double x,y;
  bool operator<( const point &u ) const {
      //return x < u.y;
      if(x != u.x) return x < u.x;
        return y < u.y;
  }
};
point a[100000];

double dis(point a,point b){
  return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}

double merge(int left,int right){
  if(left+1 == right) return dis(a[left],a[right]);
  int mid = (left+right)/2;
  double xm = min(merge(left,mid),merge(mid,right));

  vector<point> vec;
  for(int i = left; i <= right; i++){
    if(abs(a[mid].x-a[i].x) <= xm){
      vec.push_back({a[i].y,a[i].x});
    }
  }
  sort(vec.begin(),vec.end());
  for(int i = 0; i < vec.size(); i++){
    for(int j = i+1; j < vec.size(); j++){
      if(vec[j].x-vec[i].x > xm) break;
      xm = min(xm,dis(vec[i],vec[j]));
    }
  }
  return xm;
}

signed main(){

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

  sort(a,a+n);
  printf("%.10f\n",(merge(0,n-1)));

  return 0;
}