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

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)

using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef pair<int, int> PI;
const double EPS=1e-9;

const int N = 1e5 + 10;
double x[N], y[N];

struct x_cmp {
  bool operator() (int i, int j) {
    return x[i] < x[j];
  }
};
struct y_cmp {
  bool operator() (int i, int j) {
    return y[i] < y[j];
  }
};

double dist2(int i, int j) {
  return pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2);
}

double min_brute_force(const std::vector<int> & v) {
  double mi = 1.0 / 0.0;
  int n = v.size();
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      if (i == j) {
	continue;
      }
      mi = min(mi, dist2(v[i], v[j]));
    }
  }
  return mi;
}


double min_strip(const vector<int> &v, double d) {
  double mi = d;
  int n = v.size();
  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n && pow(y[v[j]] - y[v[i]], 2) < mi; ++j) {
      mi = min(mi, dist2(v[i], v[j]));
    }
  }
  return mi;
}

/*
 */
double min_pair_util(const vector<int> &vx) {
  int n = vx.size();
  if (n <= 4) {
    return min_brute_force(vx);
  }
  // divide at middle
  int mid = n / 2;
  double mid_x = x[vx[mid]];
  double ml = min_pair_util(vector<int>(vx.begin(), vx.begin() + mid));
  double mr = min_pair_util(vector<int>(vx.begin() + mid, vx.end()));
  double dist = min(ml, mr);
  vector<int> strip;
  for(int i = 0; i < n; ++i) {
    if (pow(x[vx[i]] - mid_x, 2) < dist) {
      strip.push_back(vx[i]);
    }
  }
  sort(strip.begin(), strip.end(), y_cmp());
  double res = min_strip(strip, dist);
  return res;
}

int main(void){
  int n;
  cin >> n;
  REP(i, 0, n) {
    cin >> x[i] >> y[i];
  }
  double mi = 1e10;
  vector<int> v(n);
  REP(i, 0, n) {
    v[i] = i;
  }
  sort(v.begin(), v.end(), x_cmp());
  mi = min_pair_util(v);
  printf("%.9f\n", sqrt(mi));
}