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 <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define all(c) begin(c), end(c)
#define dump(x) cerr << __LINE__ << ":\t" #x " = " << x << endl

using ld = long double;
using P = complex<ld>;
using G = vector<P>;
const ld pi = acos(-1);

namespace std {
    bool operator < (const P& a, const P& b) {
        return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
    }
}

template<class iter>
tuple<ld, P, P> closest_pair(iter left, iter right) {
    int n = distance(left, right);
    if(n <= 1) return make_tuple(numeric_limits<ld>::max(), *left, *left);
    iter middle = next(left, n/2);
    ld x = middle->real();
    auto d = min(closest_pair(left, middle), closest_pair(middle, right));
    inplace_merge(left, middle, right, [](const P &a, const P &b){
            return a.imag() < b.imag();
        });
    vector<iter> around;
    for(iter i = left; i != right; ++i){
        ld dx = fabs(i->real() - x);
        ld &opt = get<0>(d);
        if(dx*dx >= opt) continue;
        for(auto j = around.rbegin(); j != around.rend(); ++j){
            ld dx = i->real() - (**j).real();
            ld dy = i->imag() - (**j).imag();
            if(dy*dy >= opt) break;
            ld norm = dx*dx + dy*dy;
            if(get<0>(d) > norm){
                d = make_tuple(norm, *i, **j);
            }
        }
        around.push_back(i);
    }
    return d;
};

// http://www.spoj.com/problems/CLOPPAIR/
// 18124516

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout << fixed << setprecision(6) << endl;
    int n;
    cin >> n;
    vector<P> a;
    map<P,int> idx;
    rep(i,n){
        ld x,y;
        cin >> x >> y;
        a.emplace_back(x,y);
        idx[P(x,y)] = i;
    }
    ld z;
    P x, y;
    sort(all(a));
    tie(z, x, y) = closest_pair(all(a));
    int A = idx[x], B = idx[y];
    if(A > B) swap(A, B);
    cout << sqrt(z) << endl;
}