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 db = double;
const db Inf = 1e18L;

struct poi {
	db x, y;
	poi operator -(poi p) {
		return {x - p.x, y - p.y};
	}
	bool operator <(poi p) const {
		return tie(x, y) < tie(p.x, p.y);
	}
	db len2() {
		return x * x + y * y;
	}
};

using vp = vector <poi>;
db solve(poi *p, int l, int r) {
	if(l + 1 == r) return Inf;
	int m = (l + r) / 2; db mx = p[m].x; vector <poi> v;
	db ret = min(solve(p, l, m), solve(p, m, r));
	for(int i = l; i < r; i ++)
		if(poi{p[i].x - mx, 0}.len2() < ret)
			v.push_back(p[i]);
	sort(v.begin(), v.end(), [](poi a, poi b) {
		return tie(a.y, a.x) < tie(b.y, b.x); });
	for(int i = 0; i < v.size(); i ++)
		for(int j = i + 1; j < v.size(); j ++) {
			if(poi{0, v[i].y - v[j].y}.len2() > ret) break;
			ret = min(ret, (v[i] - v[j]).len2());
		}
	return ret;
} // ?????????p[]????????????

const int N = 1e5L + 11;
poi p[N];

int main() {
	ios :: sync_with_stdio(false);
	int n; cin >> n;
	for(int i = 0; i < n; i ++)
		cin >> p[i].x >> p[i].y;
	sort(p, p + n);
	db ans = solve(p, 0, n);
	cout << fixed << setprecision(9) << sqrt(ans) << '\n';
	return 0;
}