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
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <climits>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
#include <random>
#include <cctype>
#include <complex>
#include <regex>

using namespace std;

#define C_MAX(a, b) ((a)>(b)?(a):(b))
#define SHOW_VECTOR(v) {std::cerr << #v << "\t:";for(const auto& xxx : v){std::cerr << xxx << " ";}std::cerr << "\n";}
#define SHOW_MAP(v){std::cerr << #v << endl; for(const auto& xxx: v){std::cerr << xxx.first << " " << xxx.second << "\n";}}

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;

}