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;

#define int long long
#define endl '\n'
#define maxn 100010
const int MOD = 1000000007;

int n;

double closest_pair(vector<pair<double, double>> &v) {
    sort(v.begin(), v.end());
    double ans = DBL_MAX;
    set<pair<double, double>> box;
    int lt = 0;
    box.insert({v.front().second, v.front().first});
    for (int i = 1; i < n; i++) {
        while (lt < i and v[i].first - v[lt].first > ans)box.erase({v[lt].second, v[lt].first}), lt++;
        for (auto it = box.lower_bound({v[i].second - ans, v[i].first - ans});
             it != box.end() and v[i].second + ans >= it->first; it++) {
            ans = min(ans, sqrt(pow(v[i].first - it->second, 2) + pow(v[i].second - it->first, 2)));
        }
        box.insert({v[i].second, v[i].first});
    }
    return ans;
}

void solve() {
    cin >> n;
    vector<pair<double, double>> v(n);
    for (int i = 0; i < n; i++)cin >> v[i].first >> v[i].second;
    cout << fixed << setprecision(10) << closest_pair(v) << endl;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
//    cin >> t;

    while (t--)
        solve();
    return 0;
}