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 <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

struct Info{
	Info(){
		x = y = 0;
	}
	Info(double arg_x,double arg_y){
		x = arg_x;
		y = arg_y;
	}
	bool operator<(const struct Info &arg) const{
			return x < arg.x;
	};
	double x,y;
};

int N;

bool compare_y(Info left,Info right){
	return left.y < right.y;
}

Info* info;

double closest_pair(Info* array,int tmp_N){
	if(tmp_N <= 1)return DBL_MAX;

	int mid = tmp_N/2;
	double x = array[mid].x;
	double dist = min(closest_pair(array,mid),closest_pair(array+mid,tmp_N-mid));
	inplace_merge(array,array+mid,array+tmp_N,compare_y);

	vector<Info> V;
	for(int i = 0; i < tmp_N; i++){
		if(fabs(array[i].x-x) >= dist)continue;

		for(int j = 0; j < V.size();j++){
			double dx = array[i].x - V[V.size()-j-1].x;
			double dy = array[i].y - V[V.size()-j-1].y;
			if(dy >= dist)break;
			dist = min(dist,sqrt(dx*dx+dy*dy));
		}
		V.push_back(array[i]);
	}
	return dist;
}

int main(){

	scanf("%d",&N);
	info = (Info*)malloc(sizeof(Info)*N);

	for(int i = 0; i < N; i++){
		scanf("%lf %lf",&info[i].x,&info[i].y);
	}

	sort(info,info+N);

	printf("%.7lf\n",closest_pair(info,N));

	return 0;
}