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;
using ld = long double;
using vi = vector<int>;    using vvi = vector<vi>;
using vb = vector<bool>;   using vvb = vector<vb>;
using vl = vector<ll>;     using vvl = vector<vl>;
using vd = vector<double>; using vvd = vector<vd>;

#define REP(i,n) for(ll i = 0; i < (n); ++i)
#define ALL(c) (c).begin(), (c).end()
#define FOR(i,s,e) for (ll i = s; i < (ll)e; i++)
#define TEN(x) ((ll)1e##x)
const ll mod = TEN(9) + 7;

template<class T>
double closest_pair(vector<pair<T, T>> a, double inf = 1e15) {
	using P = pair<T, T>;
	using Iterator = typename vector<P>::iterator;
	function<double(Iterator, ll)> recur = [&](Iterator it, ll len) {
		if (len <= 1) return inf;
		ll half = len / 2;
		T x = (it + half)->first;
		double min_d = min(recur(it, half), recur(it + half, len - half));
		inplace_merge(
			it, it + half, it + len,
			[](P lhs, P rhs) { return lhs.second < rhs.second; }
		);

		vector<P> b;
		REP(i, len) {
			if (fabs((it + i)->first - x) >= min_d) continue;
			REP(j, b.size()) {
				double dx = (it + i)->first - b[b.size() - j - 1].first;
				double dy = (it + i)->second - b[b.size() - j - 1].second;
				if (dy >= min_d) break;
				min_d = min(min_d, sqrt(dx * dx + dy * dy));
			}
			b.push_back(*(it + i));
		}

		return min_d;
	};
	sort(a.begin(), a.end());
	return recur(a.begin(), a.size());
}

int main() {
#ifdef INPUT_FROM_FILE
	ifstream cin("sample.in");
	ofstream cout("sample.out");
#endif
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(50);

	ll n; cin >> n;
	vector<pair<double, double>> a(n);
	REP(i, n) cin >> a[i].first >> a[i].second;
	cout << closest_pair(a) << endl;

	return 0;
}