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 <cstdio>
#include <vector>
#include <complex>
#include <cmath>
#include <utility>
#include <algorithm>
#include <map>
#include <cstdlib>
#include <ctime>
using namespace std;

typedef pair<int,int> pii;
typedef complex<double> P;


pii topii(const P &p, double d){
	return pii(real(p) / d, imag(p) / d);
}


int main(){
	srand(time(0));

	int n;
	scanf("%d", &n);
	double x, y;
	vector<P> v(n);
	for(int i = 0; i < n; ++i){
		scanf("%lf%lf", &x, &y);
		v[i] = P(x + 100.0, y + 100.0);
	}
	random_shuffle(v.begin(), v.end());

	double ans = 500.0;
	map<pii,vector<int> > mp;
	map<pii,vector<int> >::iterator it;
	for(int i = 0; i < n; ++i){
		double mdis = ans;

		pii p = topii(v[i], ans);
		for(int dy = -1; dy <= 1; ++dy)
		for(int dx = -1; dx <= 1; ++dx){
			it = mp.find(pii(p.first + dy, p.second + dx));
			if(it != mp.end()){
				for(int j = it->second.size(); j--; ){
					int k = it->second[j];
					mdis = min(mdis, abs(v[i] - v[k]));
				}
			}
		}
		
		if(mdis < ans){
			ans = mdis;
			mp.clear();
			for(int j = 0; j < i; ++j){
				mp[topii(v[j], ans)].push_back(j);
			}
		}
		mp[topii(v[i], ans)].push_back(i);
	}
	
	printf("%.8f\n", ans);
}