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:
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4,sse4.1,sse4.2,avx,avx2,tune=native")
#include <bits/stdc++.h>

#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
const int MD = (int)1e9 + 7; typedef vector<ll> VL;
void dbg(){ cerr << "\n"; }  template <class T, class ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }
template <class T> void amax(T& a,T b){ if(a>b) a=b;}

using Pt = pair<double, double>;
bool compare_y(Pt a, Pt b){return a.second < b.second;};
double closest_pair(vector<Pt>& pos, int l, int r){
	if(r-l <=1) return 1e111;
	int mid = (l+r) /2 ;
	double x = pos[mid].first;
	double d = min(closest_pair(pos, l, mid), closest_pair(pos, mid, r));
	auto it = pos.begin(), itl = it+l, itm = it+mid, itr= it+r;
	inplace_merge(itl, itm, itr, compare_y);
	
	vector<Pt> near_line;
	rep2(i, l, r){
		if(abs(pos[i].first - x) >= d) continue;
		int m = sz(near_line);
		repr(j, m-1, 0){
			double px = pos[i].first  - near_line[j].first;
			double py = pos[i].second - near_line[j].second;
			if(py >= d) break;
			d = min(d, sqrt(px*px + py*py));
		}
		near_line.emplace_back(pos[i]);
	}
	return d;
}

int main(){
	//cin.tie(0); ios_base::sync_with_stdio(false);
	int n;
	cin >>n;
	vector<Pt> v(n);
	rep(i, n) cin >>v[i].first >>v[i].second;
	sort(all(v));
	auto ans = closest_pair(v, 0, n);
	printf("%.14f\n", ans);
	return 0;
}