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 <cmath>
#include <iostream>
 
template <typename T>
struct Point { 
    T x, y;
    explicit constexpr Point() : x(0), y(0) {}
    explicit constexpr Point(T _x, T _y) : x(_x), y(_y) {}
    const Point operator + (const Point& p) const { return Point(x + p.x, y + p.y);}
    const Point operator - (const Point& p) const { return Point(x - p.x, y - p.y);}
    Point& operator *= (const T& p) { x *= p, y *= p; return *this;}
    Point& operator += (const T& p) { x += p, y += p; return *this;}
    Point& operator -= (const T& p) { x -= p, y -= p; return *this;}
    Point& operator /= (const T& p) { x /= p; y /= p; return *this;}
    Point& operator += (const Point& p) { x += p.x, y += p.y; return *this;}
    Point& operator -= (const Point& p) { x -= p.x, y -= p.y; return *this;}
    const T dot(const Point& q) { return x * q.x + y * q.y;}
    const T norm() { return sqrt(x * x + y * y);}
    friend std::ostream& operator<<(std::ostream& os, const Point& p) { os << "(" << p.x << ", " << p.y << ")"; return os;}
};
 
#include <vector>
#include <iomanip>
#include <functional>
#include <tuple>
#include <algorithm>
using namespace std;
using Pt = Point<double>;
const double INF = 1e18;
const double EPS = 1.0e-11;
bool eq(double a, double b) { return fabs(a - b) <= EPS;}
int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n_;
    cin >> n_;
    vector<Pt> points(n_);
    for(auto& p : points)
        cin >> p.x >> p.y;
    sort(points.begin(), points.end(), [](const Pt& l, const Pt& r) {
            return eq(l.x, r.x) ? l.y < r.y : l.x < r.x;
        });
    function<double(int, int)> closest = [&](int id, int n) {
        if(n <= 1) return INF;
        int m = n / 2;
        double boundX = points[id + m].x;
        double res = min(closest(id, m), closest(id + m, n - m));
        auto fit = points.begin() + id;
        inplace_merge(fit, fit + m, fit + n, [](const Pt& l, const Pt& r) {
                return  eq(l.y, r.y) ? l.x < r.x : l.y < r.y;
            });
        vector<int> memo;
        for(int i = id; i < id + n; ++i) {
            if(fabs(boundX - points[i].x) >= res) continue;
            for(int j = -1 + memo.size(); j >= 0; --j) {
                Pt p = points[i] - points[memo[j]];
                if(p.y >= res) break;
                res = min(res, p.norm());
            }
            memo.emplace_back(i);
        }
        return res;
    };
    cout << fixed << setprecision(10) << closest(0, n_) << endl;
    return 0;
}