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<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<ctime>
#include<vector>

using namespace std;

#define eps 0.0000000001

struct vec{
  double x, y;
  void nextvec(){ scanf("%lf %lf", &x, &y); return; }
  vec operator+(const vec& a) const { return (vec){x + a.x, y + a.y}; }
  vec operator-(const vec& a) const { return (vec){x - a.x, y - a.y}; }
  vec operator*(const double& k) const { return (vec){k * x, k * y}; }
  vec sca(double t){ return (vec){t * x, t * y}; }
  double dot(vec a){ return x * a.x + y * a.y; }
  double cross(vec a){ return x * a.y - y * a.x; }
  double norm(){ return sqrt(x * x + y * y); }
  double norm2(){ return x * x + y * y; }
};

bool xsort(vec qwe, vec rty){ return qwe.x < rty.x; }
bool ysort(vec qwe, vec rty){ return qwe.y < rty.y; }

vec pt[100000];
vec ytmp[100000];
vec ymerge[100000];
double ma = 100000000000.0;

double closestpair(int l, int r){
  if(r - l <= 1)return ma;
  int m = l + (r - l) / 2;
  double xm = pt[m].x;
  double res = min(closestpair(l, m), closestpair(m, r));

  int hdmerge = 0, hdtmp = 0, lhd = l, rhd = m;
  vec now;
  for(;;){
    if(lhd == m && rhd == r)break;
    else if(rhd == r)now = pt[lhd++];
    else if(lhd == m)now = pt[rhd++];
    else if(ysort(pt[lhd], pt[rhd]))now = pt[lhd++];
    else now = pt[rhd++];

    ymerge[hdmerge++] = now;
    if(abs(now.x - xm) <= res + eps){
      ytmp[hdtmp++] = now;
      for(int i = hdtmp - 2;i >= 0;--i){
        if(abs(ytmp[i].y - now.y) >= res - eps)break;
        res = min(res, (now - ytmp[i]).norm());
      }
    }
  }
  for(int i = l;i < r;++i)pt[i] = ymerge[i - l];

  return res;
}

signed main(void){
  int n;
  scanf("%d", &n);
  for(int i = 0;i < n;++i)pt[i].nextvec();
  sort(pt, pt + n, xsort);
  printf("%.13lf\n", closestpair(0, n));

  return 0;
}