Problem: You are given N non-overlapping circles in xy-plane. The radius of each circle varies, but the radius of the largest circle is not double longer than that of the smallest.

<image>

Figure 1: The Sample Input

The distance between two circles C1 and C2 is given by the usual formula

<image>

where (xi, yi ) is the coordinates of the center of the circle Ci, and ri is the radius of Ci, for i = 1, 2.

Your task is to write a program that finds the closest pair of circles and print their distance.



Input

The input consists of a series of test cases, followed by a single line only containing a single zero, which indicates the end of input.

Each test case begins with a line containing an integer N (2 ≤ N ≤ 100000), which indicates the number of circles in the test case. N lines describing the circles follow. Each of the N lines has three decimal numbers R, X, and Y. R represents the radius of the circle. X and Y represent the x- and y-coordinates of the center of the circle, respectively.

Output

For each test case, print the distance between the closest circles. You may print any number of digits after the decimal point, but the error must not exceed 0.00001.

Example

Input

4
1.0 0.0 0.0
1.5 0.0 3.0
2.0 4.0 0.0
1.0 3.0 4.0
0


Output

0.5

Solution (in CPP):

Solution:
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
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{
	bool operator<(const struct Info &arg) const{
		if(x != arg.x){
			return x < arg.x;
		}else{
			return y < arg.y;
		}
	}
	double x,y,r;
};

int N;
Info info[100001];

bool compare_y(Info left,Info right){ //順序付け関数

	return left.y < right.y;

}

bool is_OK(int index,double x,double dist){
	if(info[index].x < x){ //基準線より中心が左
		if(info[index].x+info[index].r+dist < x){
			return false;
		}

	}else{ //基準線より中心が右
		if(info[index].x-info[index].r-dist > x){
			return false;
		}
	}

	return true;
}

double calc_dist(int a,int b){
	return sqrt((info[a].x-info[b].x)*(info[a].x-info[b].x)+(info[a].y-info[b].y)*(info[a].y-info[b].y))-(info[a].r+info[b].r);
}

double calc_y_dist(int a,int b){
	return (info[b].y-info[b].r)-(info[a].y+info[a].r);
}

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; //基準線x
	double dist = min(closest_pair(array,mid),closest_pair(array+mid,tmp_N-mid)); //集合を2分割し、再帰的に最小距離を求める
	inplace_merge(array,array+mid,array+tmp_N,compare_y); //2つのソート済の範囲をマージ

	vector<int> V; //★★再帰毎にメモリを確保(indexをpush)★★


	int left,right,m,search_left;

	for(int i = 0; i < tmp_N; i++){
		//if(!is_OK(i,x,dist))continue; //基準線より最小距離以上離れている点は無視(★異なる領域間での、新最小値を作り得ないということ★)

		//★★Vはyの昇順に並んでいる:自分よりy座標が小さいもののみ、入っている★★

		//2分探索で、検索範囲を定める
		/*left = 0,right = V.size()-1,m = (left+right)/2;
		search_left = 0;

		while(left <= right){
			if(calc_y_dist(V[m],i) < dist){ //y座標の差がdist未満
				search_left = m;
				right = m-1; //より左へ
			}else{
				left = m+1; //より右へ
			}
			m = (left+right)/2;
		}*/

		/*for(int k = search_left; k < V.size(); k++){
			dist = min(dist,calc_dist(V[k],i));
		}*/

		for(int k = 0; k < min((int)V.size(),2); k++){
			dist = min(dist,calc_dist(V[V.size()-1-k],i));
		}

		V.push_back(i); //可能性あり集合に、iを追加
	}
	return dist;
}

void func(){

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

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

int main(){

	while(true){
		scanf("%d",&N);
		if(N == 0)break;

		func();
	}

	return 0;
}