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


class ClosestPair {
private:
  std::vector<double> x, y;
  struct x_cmp {
    const ClosestPair &cp;
    x_cmp(const ClosestPair &cp) : cp(cp) {} 
    bool operator() (int i, int j) {
      return cp.x[i] < cp.x[j];
    }
  };
  struct y_cmp {
    const ClosestPair &cp;
    y_cmp(const ClosestPair &cp) : cp(cp) {} 
    bool operator() (int i, int j) {
      return cp.y[i] < cp.y[j];
    }
  };
  x_cmp xc;
  y_cmp yc;
  double dist2(int i, int j) const {
    return pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2);
  }

  double min_brute_force(const std::vector<int> & v) const {
    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 = std::min(mi, dist2(v[i], v[j]));
      }
    }
    return mi;
  }


  double min_strip(const std::vector<int> &v, double d) const {
    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 = std::min(mi, dist2(v[i], v[j]));
      }
    }
    return mi;
  }

  /*
   */
  double min_pair_util(const std::vector<int> &vx) const {
    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(std::vector<int>(vx.begin(), vx.begin() + mid));
    double mr = min_pair_util(std::vector<int>(vx.begin() + mid, vx.end()));
    double dist = std::min(ml, mr);
    std::vector<int> strip;
    for(int i = 0; i < n; ++i) {
      if (pow(x[vx[i]] - mid_x, 2) < dist) {
	strip.push_back(vx[i]);
      }
    }
    std::sort(strip.begin(), strip.end(), yc);
    double res = min_strip(strip, dist);
    return res;
  }
  ClosestPair(const std::vector<double> &xs, const std::vector<double> &ys) : x(xs), y(ys), xc(*this), yc(*this) {
  }
  double internal_solve(void) const {
    int n = x.size();
    std::vector<int> v(n);
    for (int i = 0; i < n; ++i) {
      v[i] = i;
    }
    std::sort(v.begin(), v.end(), xc);
    return std::sqrt(min_pair_util(v));
  }
public:
  static double solve(const std::vector<double> &xs, const std::vector<double> &ys) {
    return ClosestPair(xs, ys).internal_solve();    
  }
};
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)

#include <cstdio>
#include <iostream>

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

int main(void){
  int n;
  cin >> n;
  vector<double> x(n), y(n);
  REP(i, 0, n) {
    cin >> x[i] >> y[i];
  }
  printf("%.9f\n", ClosestPair::solve(x, y));
}