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:
#pragma GCC optimize("O3")
//#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx2")
#define io_init cin.tie(0);ios::sync_with_stdio(0);cout<<setprecision(20)
#include <bits/stdc++.h>
constexpr int INF = 2147483647;
constexpr long long int INF_LL = 9223372036854775807;
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979323846;
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

typedef complex<double> P;
 
 bool comp_x(const P &a, const P &b) {
     return a.real() < b.real();
 }
 
 bool comp_y(const P &a, const P &b) {
     return a.imag() < b.imag();
 }
 
 double getClosePair(vector<P> &a, int l, int r) {
     if (r - l <= 1) return 1e20;
     int mid = (l + r) / 2;
     double X = a[mid].real();
     double d = min(getClosePair(a, l, mid), getClosePair(a, mid, r));
     inplace_merge(a.begin() + l, a.begin() + mid, a.begin() + r, comp_y);
 
     vector<P> b;
     for (int i = l; i < r; i++) {
         if (abs(a[i].real() - X) >= d) continue;
         for (int j = b.size() - 1; j >= 0; j--) {
             if (abs((a[i] - b[j]).imag()) >= d) break;
             d = min(d, abs(a[i] - b[j]));
         }
         b.push_back(a[i]);
     }
     return d;
 }
 
 int main() {
 
     int N;
     cin >> N;
 
     vector<P> p(N);
     for (int i = 0; i < N; i++) {
         double x, y;
         cin >> x >> y;
         p[i] = P(x, y);
     }
 
     sort(p.begin(), p.end(), comp_x);
 
     double ans = getClosePair(p, 0, N);
     cout << fixed << setprecision(20) << ans << endl;
 
 }