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>
#define lb long double
#define N 100010
#define eps 1e-11
#define INF 1e18
using namespace std;
struct Po{lb x,y;}x;
vector<Po> no;
int n;
Po operator -(Po x,Po y){return (Po){x.x-y.x,x.y-y.y};}
void get(Po &x){scanf("%Lf %Lf",&x.x,&x.y);}
bool c1(const Po &x,const Po &y){if (fabs(x.x-y.x)<eps)return x.y<y.y;return x.x<y.x;}
bool c2(const Po &x,const Po &y){return x.y<y.y;}
lb dis(Po x){return sqrtl(x.x*x.x+x.y*x.y);}
lb que(vector<Po> x){
	if (x.size()==1) return INF;
	if (x.size()==2) return dis(x[0]-x[1]);
	int mid=x.size()/2;
	vector<Po> s1,s2;
	s1.clear();s2.clear();
	for (int i=0;i<x.size();i++)if (i<mid) s1.push_back(x[i]);else s2.push_back(x[i]);
	lb an=min(que(s1),que(s2));
	reverse(s1.begin(),s1.end());
	while (s1.size()&&fabs(x[mid].x-s1[s1.size()-1].x)>an-eps)s1.pop_back();
	while (s2.size()&&fabs(s2[s2.size()-1].x-x[mid-1].x)>an-eps)s2.pop_back();
	sort(s1.begin(),s1.end(),c2);
	sort(s2.begin(),s2.end(),c2);
	int l=0,r=-1;
	for (int i=0;i<s1.size();i++){
		while (r+1<s2.size()&&s2[r+1].y-s1[i].y<an+eps) r++;
		while (l+1<=s2.size()&&s1[i].y-s2[l].y>an+eps)l++;
		for (int j=l;j<=r;j++) an=min(an,dis(s2[j]-s1[i]));
	}
	return an;
}
int main(){
	scanf("%d",&n);
	while(n--){get(x);no.push_back(x);}
	sort(no.begin(),no.end(),c1);
	printf("%.10Lf",que(no));
	lb ansn=INF;
	return 0;
}