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:
// http://ir5.hatenablog.com/entry/20131221/1387557630
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <utility>
#include <cmath>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define DEBUG(x) cerr << #x << " = " << x << endl
typedef pair<double, double> P;
typedef pair<int, int> IP;
double norm(P a, P b) {
  double x = a.first - b.first;
  double y = a.second - b.second;
  return sqrt(x*x + y*y);
}
int main() {
  int N; cin >> N;
  vector<P> p(N);
  REP(i,N) {
    double x, y; cin >> x >> y;
    p[i] = make_pair(x, y);
  }
  double xmin = p[0].first, ymin = p[0].second;
  REP(i,N) {
    xmin = min(xmin, p[i].first);
    ymin = min(ymin, p[i].second);
  }
  REP(i,N) {
    p[i].first -= xmin;
    p[i].second -= ymin;
  }
  // std::rand is often used.
  random_shuffle(p.begin(), p.end());
  double delta = norm(p[0], p[1]);
  multimap<IP, int> S;
  S.insert(make_pair(IP(p[0].first / delta, p[0].second / delta), 0));
  S.insert(make_pair(IP(p[1].first / delta, p[1].second / delta), 1));
  for(int i = 2; i < N; ++i) {
    IP ip(p[i].first / delta, p[i].second / delta);
    bool update = false;
    for(int dx = -1; dx <= 1; ++dx) for(int dy = -1; dy <= 1; ++dy) {
      int count = S.count(IP(ip.first + dx, ip.second + dy));
      auto it = S.find(IP(ip.first + dx, ip.second + dy));
      for(int j = 0; j < count; ++j) {
        double d2 = norm(p[i], p[it->second]);
        if(delta > d2) {
          delta = d2;
          update = true;
        }
        ++it;
      }
    }
    if(update) {
      S.clear();
      for(int j = 0; j <= i; ++j) {
        S.insert(make_pair(IP(p[j].first / delta, p[j].second / delta), j));
      }
    }
    else {
      S.insert(make_pair(ip, i));
    }
  }
  cout.setf(ios::fixed);
  cout.precision(6);
  cout << delta << endl;
}