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>           // printf(), scanf()
#include <cmath>            // fabs(), sqrt()
#include <vector>
#include <utility>          // pair
#include <algorithm>        // sort(), inplace_merge()

using namespace std;
typedef pair<double, double> P; // first ??? x ??§?¨????second ??? y ??§?¨?

static const int MAX_N = 100000;
static const int INF = 1000000000;

P A[MAX_N];
int N;

bool
cmp_func(P a, P b)
{
	return a.second < b.second;
}

double
closest_pair(P* a, int n)
{
	double t;

	if (n <= 1)
		return INF;

	int m = n / 2;
	double x = a[m].first;
	double d = closest_pair(a, m); // (1)
	t = closest_pair(a + m, n - m);
	if (t < d)
		d = t;

	inplace_merge(a, a + m, a + n, cmp_func); // ??????????????????????????????????????????
	// ??????????????§ a ??? y ??§?¨??????????????????£?????????

	//x (2')
	vector<P> b; // ??´??????????????¢ d ????????????????????\????????????
	for (int i = 0; i < n; ++i)
	{
		if (fabs(a[i].first - x) >= d)
			continue;

		// b ?????\??£?????????????????????????°??????????y ??§?¨?????????? d ??\?????????????????§????????????
		for (unsigned int j = 0; j < b.size(); ++j)
		{
			double dx = a[i].first - b[b.size() - j - 1].first;
			double dy = a[i].second - b[b.size() - j - 1].second;
			if (dy >= d)
				break;

			t = sqrt(dx * dx + dy * dy);
			if (t < d)
				d = t;
		}

		b.push_back(a[i]);
	}

	return d;
}

int
main(int argc, char** argv)
{
	scanf("%d", &N);
	for (int i = 0; i < N; ++i)
		scanf("%lf %lf", &A[i].first, &A[i].second);

	sort(A, A + N);
	printf("%.10f\n", closest_pair(A, N));
	return 0;
}