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 <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<long long> vll;
typedef pair<int,int> pint;
typedef pair<long long, long long> pll;

#define MP make_pair
#define PB push_back
#define ALL(s) (s).begin(),(s).end()
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P) 
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P) 
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P) 
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s; }



typedef double DD;

const DD INF = 1LL<<60;
const DD EPS = 1e-10;
const DD PI = acos(-1.0);
DD torad(int deg) {return (DD)(deg) * PI / 180;}
DD todeg(DD ang) {return ang * 180 / PI;}

struct Point {
    DD x, y;
    Point(DD x = 0.0, DD y = 0.0) : x(x), y(y) {}
    friend ostream& operator << (ostream &s, const Point &p) {return s << '(' << p.x << ", " << p.y << ')';}
};

Point operator + (const Point &p, const Point &q) {return Point(p.x + q.x, p.y + q.y);}
Point operator - (const Point &p, const Point &q) {return Point(p.x - q.x, p.y - q.y);}
Point operator * (const Point &p, DD a) {return Point(p.x * a, p.y * a);}
Point operator * (DD a, const Point &p) {return Point(a * p.x, a * p.y);}
Point operator * (const Point &p, const Point &q) {return Point(p.x * q.x - p.y * q.y, p.x * q.y + p.y * q.x);}
Point operator / (const Point &p, DD a) {return Point(p.x / a, p.y / a);}
Point conj(const Point &p) {return Point(p.x, -p.y);}
Point rot(const Point &p, DD ang) {return Point(cos(ang) * p.x - sin(ang) * p.y, sin(ang) * p.x + cos(ang) * p.y);}
Point rot90(const Point &p) {return Point(-p.y, p.x);}
DD cross(const Point &p, const Point &q) {return p.x * q.y - p.y * q.x;}
DD dot(const Point &p, const Point &q) {return p.x * q.x + p.y * q.y;}
DD norm(const Point &p) {return dot(p, p);}
DD abs(const Point &p) {return sqrt(dot(p, p));}
DD amp(const Point &p) {DD res = atan2(p.y, p.x); if (res < 0) res += PI*2; return res;}
bool eq(const Point &p, const Point &q) {return abs(p - q) < EPS;}
bool operator < (const Point &p, const Point &q) {return (abs(p.x - q.x) > EPS ? p.x < q.x : p.y < q.y);}
bool operator > (const Point &p, const Point &q) {return (abs(p.x - q.x) > EPS ? p.x > q.x : p.y > q.y);}
Point operator / (const Point &p, const Point &q) {return p * conj(q) / norm(q);}

int ccw(const Point &a, const Point &b, const Point &c) {
    if (cross(b-a, c-a) > EPS) return 1;
    if (cross(b-a, c-a) < -EPS) return -1;
    if (dot(b-a, c-a) < -EPS) return 2;
    if (norm(b-a) < norm(c-a) - EPS) return -2;
    return 0;
}

struct Line : vector<Point> {
    Line(Point a = Point(0.0, 0.0), Point b = Point(0.0, 0.0)) {
        this->push_back(a);
        this->push_back(b);
    }
};

struct Circle : Point{
    DD r;
    Circle(Point p = Point(0.0, 0.0), DD r = 0.0) : Point(p), r(r) {}
};


DD MAX_R;
bool compare_y(Circle a, Circle b) { return a.y < b.y; }

DD Rec(vector<Circle>::iterator it, int n) {
    if (n <= 1) return INF;
    int m = n/2;
    DD x = it[m].x;
    DD d = min(Rec(it, m), Rec(it+m, n-m));
    inplace_merge(it, it+m, it+n, compare_y);
    
    vector<Circle> vec;
    for (int i = 0; i < n; ++i) {
        if (fabs(it[i].x - x) >= d + MAX_R*2) continue;
        for (int j = 0; j < vec.size(); ++j) {
            DD dx = it[i].x - vec[vec.size()-j-1].x;
            DD dy = it[i].y - vec[vec.size()-j-1].y;
            if (dy >= d + MAX_R*2) break;
            d = min(d, abs(sqrt(dx*dx+dy*dy) - it[i].r - vec[vec.size()-j-1].r));
        }
        vec.push_back(it[i]);
    }
    return d;
}

DD Closet(vector<Circle> vc) {
    int n = vc.size();
    sort(vc.begin(), vc.end());
    return Rec(vc.begin(), n);
}


int n;
double r, x, y;

int main() {
    while (cin >> n) {
        if (n == 0) break;
        MAX_R = 0.0;
        vector<Circle> vc(n);
        for (int i = 0; i < n; ++i) cin >> vc[i].r >> vc[i].x >> vc[i].y, chmax(MAX_R, vc[i].r);
        double res = Closet(vc);
        cout << fixed << setprecision(9) << res << endl;
    }
    return 0;
}