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 JAVA):

Solution:
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.text.DecimalFormat;
import java.util.Arrays;
import java.util.Comparator;


public class Main{

	static class Circle {
		double r;
		double x;
		double y;

		public Circle(double r, double x, double y) {
			this.r = r;
			this.x = x;
			this.y = y;
		}

		public double getR() {
			return this.r;
		}

		public void set(double r) {
			this.r = r;
		}

		public double getX() {
			return this.x;
		}

		public void setX(double x) {
			this.x = x;
		}

		public double getY() {
			return this.y;
		}

		public void setY(double y) {
			this.y = y;
		}

		@Override
		public String toString() {
			return this.x + ", " + this.y;
		}
	}

	static Circle[] circles = null;
	static double maxRadius = 0.0;
	public static void main(String[] args) throws Exception{
		//Scanner s = new Scanner(System.in);
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		while(true) {
			int N = Integer.parseInt(br.readLine());
			if(N == 0)
				break;
			circles = new Circle[N];
			for(int i=0 ; i<N ; i++) {
				String[] tmp = br.readLine().split(" ");
				circles[i] = new Circle(Double.parseDouble(tmp[0]), Double.parseDouble(tmp[1]), Double.parseDouble(tmp[2]));
				maxRadius = Math.max(maxRadius, Double.parseDouble(tmp[0]));
			}

			Arrays.sort(circles, Comparator.comparing(Circle::getX));
			double res1 = solve(circles, 0, N-1);
			DecimalFormat fmt = new DecimalFormat("0.00000000");

			System.out.println(fmt.format(res1));
		}
	}

	static double solve(Circle[] c, int start, int end) {

		if(start == end || start > end)
			return Integer.MAX_VALUE;
		if(start == (end-1))
			return Math.hypot(c[start].x - c[end].x, c[start].y - c[end].y) - c[start].r - c[end].r;
		int middle = (start + end) / 2;

		double result = Math.sqrt((c[middle].x - c[middle+1].x)*(c[middle].x - c[middle+1].x) + (c[middle].y - c[middle+1].y)*(c[middle].y - c[middle+1].y)) - c[middle].r - c[middle+1].r;
		double result1 = solve(c, start, middle);
		double result2 = solve(c, middle+1, end);

		double distance =  Math.min(Math.min(result1, result2), result);
		int m = (start+end)/2;
		double middleP = (c[m-1].x + c[m].x) / 2;
		Circle[] cc = new Circle[end-start];
		int index = 0;
		for(int i=start ; i<end ;i++) {
			if(Math.abs(c[i].x - middleP) < distance+2*maxRadius) {
				cc[index++] = c[i];
			}
		}

		if(index <= 1)
			return distance;
		Circle[] cY = new Circle[index];
		for(int i=0 ; i<index ; i++) {
			cY[i] = cc[i];
		}
		Arrays.sort(cY, Comparator.comparing(Circle::getY));

		for(int j=0 ; j<index ; j++) {
			for(int k=j+1 ; k<index && (cY[k].y-cY[j].y < distance+2*maxRadius); k++) {
				distance = Math.min(distance, Math.hypot(cY[j].x - cY[k].x, cY[j].y - cY[k].y) - cY[j].r - cY[k].r);
			}
		}
		return distance;
	}

}