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:
/* Header {{{ */
#include <bits/stdc++.h>
using namespace std;

typedef long long readtype;
typedef long long var;
typedef long double let;

readtype read() {
  readtype a = 0, c = getchar(), s = 0;
  while (!isdigit(c)) s |= c == '-', c = getchar();
  while (isdigit(c)) a = a * 10 + c - 48, c = getchar();
  return s ? -a : a;
}

#ifdef LOCAL_LOGGER
#define logger(...) fprintf(stderr, __VA_ARGS__)
#define abortif(v, ...) if (v) {logger("Error in Line %d, Function '%s()'.\nInfo: ", __LINE__, __FUNCTION__); logger(__VA_ARGS__); exit(0);}
#else
#define logger(...);
#define abortif(v, ...);
#endif
/* }}} */

const int N = 1e5 + 1;
const let eps = 1e-8;
const let Pi = acos(-1.0);

int sign(let x) { return (x < -eps) ? -1 : (x > eps) ? 1 : 0; }

struct Point {
  let x, y;
  friend Point operator - (Point a, Point b) {
    return (Point) {a.x - b.x, a.y - b.y};
  }
  friend bool operator < (Point a, Point b) {
    if (sign(a.x - b.x) == 0) return sign(a.y - b.y) < 0;
    return sign(a.x - b.x) < 0;
  }
  Point Rotate(let sink, let cosk) {
    return (Point) {
      x * cosk - y * sink, x * sink + y * cosk
    };
  }
  let dist() {
    return sqrt(x * x + y * y);
  }
  friend let Dist(Point a, Point b) { 
    return (a - b).dist();
  }
};

Point ReadPoint() {
  Point p;
  scanf("%Lf%Lf", &p.x, &p.y);
  return p;
}

int n;
Point point[N];
int rnk[N];

int main() {
// #ifndef ONLINE_JUDGE
//   freopen("CGL_5_A.in", "r", stdin);
//   freopen("CGL_5_A.out", "w", stdout);
// #endif
// #ifdef LOCAL_LOGGER
//   freopen("CGL_5_A.log", "w", stderr);
// #endif
  srand(time(0));
  n = read();
  for (int i = 1; i <= n; ++i) point[i] = ReadPoint();
  let res = 0;
  bool have = false;
  int RD_TIME = 50;
  for (int rd = 1; rd <= RD_TIME; ++rd) {
    sort(point + 1, point + n + 1);
    for (int i = 1; i < n; ++i) {
      let tdist = Dist(point[i], point[i + 1]);
      if (!have) res = tdist, have = true;
      if (sign(res - tdist) > 0) res = tdist;
    }
    let angle = ((let) rand() / RAND_MAX) * Pi;
    let sink = sin(angle), cosk = cos(angle);
    for (int i = 1; i <= n; ++i)
      point[i] = point[i].Rotate(sink, cosk);
  }
  printf("%.8Lf\n", res);
  return 0;
}

/* ==== Makefile ==== {{{
CompileAndRun:
	make Compile
	make Run

Compile:
	g++ -o CGL_5_A CGL_5_A.cpp -g -Wall -DLOCAL_LOGGER

CompileUF:
	g++ -o CGL_5_A CGL_5_A.cpp -g -Wall -DLOCAL_LOGGER -fsanitize=undefined

Run:
	./CGL_5_A < CGL_5_A.in > CGL_5_A.out
==================
}}} */