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;
struct Point {
    double x, y;

    Point() = default;
    Point(double x, double y) : x(x), y(y) {}

    Point operator+(const Point &rhs) const {
        return Point(x + rhs.x, y + rhs.y);
    }

    Point operator-(const Point &rhs) const {
        return Point(x - rhs.x, y - rhs.y);
    }

    double operator*(const Point &rhs) const {
        return x * rhs.x + y * rhs.y;
    }

    double operator%(const Point &rhs) const {
        return x * rhs.y - y * rhs.x;
    }

    bool operator<(const Point &rhs) const {
        return x == rhs.x ? y < rhs.y : x < rhs.x;
    }
};
double dis(const Point& a, const Point& b) {
    return sqrt((a - b) * (a - b));
}

const int maxn = 1e5 + 5;
Point p[maxn];

double closest_pair(int l, int r) {
    if (l == r) return 1e9;
    if (r - l == 1) return dis(p[l], p[r]);
    int m = (l + r) >> 1;
    double d = min(closest_pair(l, m), closest_pair(m + 1, r));
    vector<int> vec;
    for (int i = m; i >= l && fabs(p[m].x - p[i].x) < d; --i) vec.push_back(i);
    for (int i = m + 1; i <= r && fabs(p[m].x - p[i].x) < d; ++i) vec.push_back(i);
    sort(vec.begin(), vec.end(), [&](int a, int b) { return p[a].y < p[b].y; });
    for (int i = 0; i < vec.size(); ++i) {
        for (int j = i + 1; j < vec.size() && fabs(p[vec[j]].y - p[vec[i]].y) < d; ++j) {
            d = min(d, dis(p[vec[i]], p[vec[j]]));
        }
    }
    return d;
}

int main() {
    int n; scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%lf%lf", &p[i].x, &p[i].y);
    sort(p, p + n);
    printf("%.20lf\n", closest_pair(0, n - 1));
}