Problem: Anchored Balloon

A balloon placed on the ground is connected to one or more anchors on the ground with ropes. Each rope is long enough to connect the balloon and the anchor. No two ropes cross each other. Figure E-1 shows such a situation.

<image>
Figure E-1: A balloon and ropes on the ground

Now the balloon takes off, and your task is to find how high the balloon can go up with keeping the rope connections. The positions of the anchors are fixed. The lengths of the ropes and the positions of the anchors are given. You may assume that these ropes have no weight and thus can be straightened up when pulled to whichever directions. Figure E-2 shows the highest position of the balloon for the situation shown in Figure E-1.

<image>
Figure E-2: The highest position of the balloon

Input

The input consists of multiple datasets, each in the following format.

> n
>  x1 y1 l1
>  ...
>  xn yn ln
>

The first line of a dataset contains an integer n (1 ≤ n ≤ 10) representing the number of the ropes. Each of the following n lines contains three integers, xi, yi, and li, separated by a single space. Pi = (xi, yi) represents the position of the anchor connecting the i-th rope, and li represents the length of the rope. You can assume that −100 ≤ xi ≤ 100, −100 ≤ yi ≤ 100, and 1 ≤ li ≤ 300. The balloon is initially placed at (0, 0) on the ground. You can ignore the size of the balloon and the anchors.

You can assume that Pi and Pj represent different positions if i ≠ j. You can also assume that the distance between Pi and (0, 0) is less than or equal to li−1. This means that the balloon can go up at least 1 unit high.

Figures E-1 and E-2 correspond to the first dataset of Sample Input below.

The end of the input is indicated by a line containing a zero.

Output

For each dataset, output a single line containing the maximum height that the balloon can go up. The error of the value should be no greater than 0.00001. No extra characters should appear in the output.

Sample Input


3
10 10 20
10 -10 20
-10 10 120
1
10 10 16
2
10 10 20
10 -10 20
2
100 0 101
-90 0 91
2
0 0 53
30 40 102
3
10 10 20
10 -10 20
-10 -10 20
3
1 5 13
5 -3 13
-3 -3 13
3
98 97 168
-82 -80 193
-99 -96 211
4
90 -100 160
-80 -80 150
90 80 150
80 80 245
4
85 -90 290
-80 -80 220
-85 90 145
85 90 170
5
0 0 4
3 0 5
-3 0 5
0 3 5
0 -3 5
10
95 -93 260
-86 96 211
91 90 177
-81 -80 124
-91 91 144
97 94 165
-90 -86 194
89 85 167
-93 -80 222
92 -84 218
0


Output for the Sample Input


17.3205081
16.0000000
17.3205081
13.8011200
53.0000000
14.1421356
12.0000000
128.3928757
94.1879092
131.1240816
4.0000000
72.2251798






Example

Input

3
10 10 20
10 -10 20
-10 10 120
1
10 10 16
2
10 10 20
10 -10 20
2
100 0 101
-90 0 91
2
0 0 53
30 40 102
3
10 10 20
10 -10 20
-10 -10 20
3
1 5 13
5 -3 13
-3 -3 13
3
98 97 168
-82 -80 193
-99 -96 211
4
90 -100 160
-80 -80 150
90 80 150
80 80 245
4
85 -90 290
-80 -80 220
-85 90 145
85 90 170
5
0 0 4
3 0 5
-3 0 5
0 3 5
0 -3 5
10
95 -93 260
-86 96 211
91 90 177
-81 -80 124
-91 91 144
97 94 165
-90 -86 194
89 85 167
-93 -80 222
92 -84 218
0


Output

17.3205081
16.0000000
17.3205081
13.8011200
53.0000000
14.1421356
12.0000000
128.3928757
94.1879092
131.1240816
4.0000000
72.2251798

Solution (in CPP):

Solution:
#include  <bits/stdc++.h>
#define range(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define rep(i,n) range(i,0,n)
using namespace std;

typedef bool B;
typedef long double D;
typedef complex<D> P;
typedef vector<P> VP;
typedef struct {P s,t;} L;
typedef vector<L> VL;
typedef struct {P c;D r;} C;
typedef vector <C> VC;

const D eps=1.0e-10;
const D pi=acos(-1.0);
template<class T> bool operator==(T a, T b){return abs(a-b)< eps;}
template<class T> bool operator< (T a, T b){return a < b-eps;}
template<class T> bool operator<=(T a, T b){return a < b+eps;}
//template<class T> int sig(T r) {return (r==0||r==-0) ? 0 : r > 0 ? 1 : -1;}
template<class T> int sig(T a,T b = 0) {return a < b ? -1 : b > a ? 1 : 0;}
#define X real()
#define Y imag()

D ip(P a, P b) {return a.X * b.X + a.Y * b.Y;}
D ep(P a, P b) {return a.X * b.Y - a.Y * b.X;}
D sq(D a) {return sqrt(max(a, (D)0));}
P vec(L l){return l.t-l.s;}
inline P input(){D x,y;cin >> x >> y; return P(x,y);}
//??\??? ???????????¬????????¨???


// ??? not verify
D toRagian(D degree){ return degree*pi/180.0;}
D ang (P p){return arg(p);}
D ang (P base, P a, P b) {return arg( (b - base) / (a - base) );} // base ??????
P rot (P base, P a, D theta){
	P tar=a-base;return base+polar(abs(tar), arg(tar)+theta );
}

// ?°???± verify AOJ CGL_1_A
P proj(P b,P p){ return b*ip(b,p)/norm(b);}
P proj(L l,P p){ return l.s+proj(vec(l),p-l.s);}
// ????°? verify AOJ CGL_1_B
P refl(L l,P p){ return proj(l,p)*D(2.0)-p; }

// ???????????? verify AOJ CGL_1_C
enum CCW{
	LEFT = 1,
	RIGHT = 2,
	BACK = 4,
	FRONT = 8,
	MID = 16,
	ON=FRONT|BACK|MID
};

inline int ccw(P base, P a, P b) {              //???a??¨???b???????????????????????????
	a -= base; b -= base;
	if (ep(a, b) > 0)
		return LEFT;    // counter clockwise
	if (ep(a, b) < 0)
		return RIGHT;   // clockwise
	if (ip(a, b) < 0)
		return BACK;    // b--base--a on line
	if (norm(a) < norm(b))
		return FRONT;   // base--a--b on line
	// otherwise
	return MID;      // base--b--a on line  a??¨b????????????????????????
}

// ?????? ??´???
// verify AOJ CGL_2_A
B iver(L a, L b) {return ip(vec(a),vec(b) )== 0.0;}
B ipar(L a, L b) {return ep(vec(a),vec(b) )== 0.0;}


// ?????¨??´?????¨????????¢??£??????????????? (s??????????????????????????§?????????????¨±?????????)
B iLL(L a,L b){return !ipar(a,b);}

B eqL(L a,L b){return !iLL(a, b) && ep(vec(a), b.s - a.s)==0;}
B iLS(L a,L b){return sig(ep(vec(a),b.s-a.s))*sig(ep(vec(a),b.t-a.s)) <= 0;}
B iLSs(L a,L b){return sig(ep(vec(a),b.s-a.s))*sig(ep(vec(a),b.t-a.s)) < 0;}

// ????????¨?????????????????????
// verify AOJ CGL_2_B
B iSS(L a,L b){
	int cwa = ccw(a.s,a.t, b.s) | ccw(a.s,a.t, b.t);
	int cwb = ccw(b.s,b.t, a.s) | ccw(b.s,b.t, a.t);
	return ((cwa | cwb) & MID) || ((cwa & cwb) == (LEFT | RIGHT));
}
B iSSs(L a,L b) {
	int cwa = ccw(a.s,a.t, b.s) | ccw(a.s,a.t, b.t);
	int cwb = ccw(b.s,b.t, a.s) | ccw(b.s,b.t, a.t);
	return (cwa & cwb) == (LEFT | RIGHT);
}

// ??????
// verify AOJ CGL_2_C
P pLL(L a,L b){ return a.s+vec(a)*ep(vec(b),b.s-a.s)/ep(vec(b),vec(a));}

// ?????¨??´???????????¢
D dLP(L l,P p){return abs( ep(vec(l),p-l.s) )/abs(vec(l));}
// ?????¨??????????????¢
D dSP(L s,P p){
	if (sig( ip( vec(s), p - s.s)) <= 0) return abs(p - s.s);
	if (sig( ip(-vec(s), p - s.t)) <= 0) return abs(p - s.t);
	return dLP(s,p);
}

// ??´?????¨??´???????????¢
D dLL(L a,L b){ return iLL(a,b)?0:dLP(a,b.s);}

// ?????¨??´?????¨????????¢??£????????¢
D dLS(L a,L b){ return iLS(a,b)?0:min(dLP(a, b.s),dLP(a, b.t));}

// ????????¨??????????????¢
// verify AOJ CGL_2_D
D dSS(L a,L b){ return iSS(a,b)?0:
	min({ dSP(a,b.s),dSP(a,b.t),dSP(b,a.s),dSP(b,a.t)});
}


// ??????????????????
inline B cmp_x(const P &a,const P &b){
	return (abs(a.X-b.X)<eps ) ?  a.Y<b.Y : a.X<b.X;
}  // base x
inline B cmp_y(const P &a,const P &b){
	return (abs(a.Y-b.Y)<eps ) ?  a.X<b.X : a.Y<b.Y;
}  // base y
inline B cmp_a(const P &a,const P &b){
	return (abs(arg(a)-arg(b))<eps ) ?  norm(a) < norm(b) : arg(a)<arg(b);
} // base arg

// ????§???¢

// ??¢???
// Verify AOJ 1100
// verify CGL_3_A
D area(VP pol){
	int n=pol.size();
	D sum=0.0;
	rep(i,n){
		D x=pol[i%n].X-pol[(i+1)%n].X;
		D y=pol[i%n].Y+pol[(i+1)%n].Y;
		sum+=x*y;
	}
	return abs(sum/2.0);
}

// ???????§???¢?????????
// verify CGL_3_B
B is_convex(VP pol){
	int n=pol.size();
	rep(i,n){
		P prev=pol[(i+n-1)%n];
		P next=pol[(i+1)%n];
		if(ccw(prev,pol[i],next)==RIGHT) return false;
	}
	return true;
}

// ????§???¢??????????????? ?????? 2 ?????? 1 ???????????? 0???(???????§???¢??????)
//verify AOJ CGL_3-C
int in_polygon(VP pol,P p){
	int n=pol.size();
	int res=0;
	rep(i,n){
		if(ccw(pol[i],pol[(i+1)%n],p)==MID)
			return 1;
		D vt=(p.Y-pol[i].Y)/(pol[(i+1)%n].Y-pol[i].Y);
		D dx=pol[(i+1)%n].X-pol[i].X;
		if((pol[i].Y<=p.Y)&&(p.Y< pol[(i+1)%n].Y)&&(p.X<pol[i].X+vt*dx))res++;
		if((pol[i].Y> p.Y)&&(p.Y>=pol[(i+1)%n].Y)&&(p.X<pol[i].X+vt*dx))res--;
	}
	return res?2:0;
}

// ????§???¢??????????????????(???????§???¢??????)
// Verify AOJ 2514

bool in_polygon(VP pol,L l){
	VP check;
	int n=pol.size();

	rep(i,n){
		L tar={pol[i],pol[(i+1)%n]};
		if(iSS(l,tar))
			check.push_back(pLL(l,tar));
	}

	check.push_back(l.s);
	check.push_back(l.t);
	sort(check.begin(),check.end(),cmp_x);
	n=check.size();
	rep(i,n-1){
		P m=(check[i]+check[i+1])/P(2.0,0.0);
		if(!in_polygon(pol,m)) return false;
	}
	return true;
}


// convex_hull
// Verify AOJ 0063
// Verify AOJ CGL_4_A
VP convex_hull(VP pol){
	int n=pol.size(),k=0;
	sort(pol.begin(),pol.end(),cmp_x);
	VP res(2*n);

	//??\??????while?????????????????????
	//????????????????????????????????????????????´??????<=0
	//???????????????????????????????????????????????´??????<0

	// down
	rep(i,n){
		while( k>1 && ep(res[k-1]-res[k-2],pol[i]-res[k-1])<0) k--;
		res[k++]=pol[i];
	}
	// up
	for(int i=n-2,t=k;i>=0;i--){
		while( k>t && ep(res[k-1]-res[k-2],pol[i]-res[k-1])<0) k--;
		res[k++]=pol[i];
	}
	res.resize(k-1);
	return res;
}

// ????????????
// verify AOJ CGL_4_C
VP convex_cut(const VP& pol, const L& l) {
	VP res;
	int n=pol.size();
	rep(i,n){
		P a = pol[i], b = pol[(i+1)%n];
		if(ccw(l.s, l.t, a) != RIGHT) res.push_back(a);
		if((ccw(l.s, l.t, a)|ccw(l.s, l.t, b))==(LEFT|RIGHT))
			res.push_back(pLL({a,b}, l));
	}
	return res;
}

// ???
// Verify AOJ 1183

enum RCC{
	A_IN_B=1,
	B_IN_A=2,
	A_ON_B=4,
	B_ON_A=8,
	ISC=16,
	ON_OUT=32,
	OUT=64,
	SAME=12,
	ONS=48
};


int rCC(C a,C b){
	D d=abs(a.c-b.c);
	int res=0;
	if(a.r+b.r< d) res|=OUT;
	if(a.r+b.r==d) res|=ON_OUT;
	if(abs(a.r-b.r) < d && d < a.r+b.r) res|=ISC;
	if(d==b.r-a.r) res|=A_ON_B;
	if(d< b.r-a.r) res|=A_IN_B;
	if(d==a.r-b.r) res|=B_ON_A;
	if(d< a.r-b.r) res|=B_IN_A;
	return res;
}

// ?????¢??£???????????????
bool iCP(C c, P p) {return sig(abs(p - c.c), c.r) <= 0;}
bool iCS(C c, L l) {return sig(c.r, dSP(l, c.c)) >= 0;}
bool iCSc(C c, L l) {return iCS(c, l) && sig(c.r, max(abs(l.s - c.c), abs(l.t - c.c))) <= 0;}

//2??????????????????
// Verify AOJ 1183

VP pCC(C a,C b){
	VP res;
	int rel=rCC(a,b);
	if(rel==SAME){   // Same
		res.push_back(a.c+P(a.r,0));
		res.push_back(a.c+P(-a.r,0));
		res.push_back(a.c+P(0,a.r));
		res.push_back(a.c+P(0,-a.r));
	}else{
		D d = abs(b.c - a.c);
		D x = (norm(d) + norm(a.r) - norm(b.r)) / (2 * d);
		P e = (b.c - a.c) / abs(b.c - a.c);
		if(rel==ISC){ // 2points
			P w = e * P(0, 1) * sq(norm(a.r)-norm(x));
			res.push_back(a.c + e * x - w);
			res.push_back(a.c + e * x + w);
		}else if(rel&ONS){ // 1points
			res.push_back(a.c + e * x);
		}
	}
	return res;
}


VP pCL(C c, L l) {
	VP res;
	P h = proj(l,c.c);
	P e = vec(l) / abs(vec(l)) * sq(norm(c.r) - norm(h - c.c));
	res.push_back(h - e);
	res.push_back(h + e);
	return res;
}


// ????????\???
// Verify AOJ 2001

L tanC(C c,D t){
	P p=c.c+polar(c.r,t);
	P d=polar(c.r,t)*P(0,1);
	return L{p-d,p+d};
}


// ????????±?????\???
// Verify AOJ 2001

VL common_tan(C a,C b){
	VL res;
	P ba=b.c-a.c;
	D d=ang(ba);
	D i=acos((a.r+b.r)/abs(ba));
	D o=acos((a.r-b.r)/abs(ba));
	int r=rCC(a,b);

	if(r==OUT){		//??±????????\???
		res.push_back(tanC(a,d+i));
		res.push_back(tanC(a,d-i));
	}

	if(r>=ISC){		// ??±????????\???
		res.push_back(tanC(a,d+o));
		res.push_back(tanC(a,d-o));
	}

	if(r&ONS) res.push_back(tanC(a,d)); //??\????????±???????????\???

	if(r==SAME) rep(i,5) res.push_back(tanC(a,i));
	return res;
}


const int vmax=1010;
struct node{int to;D cost;};
// segments arrangement
vector<node> graph[vmax];
void sArr(const vector<L> &seg, vector<P> &point){
	rep(i,seg.size()){
		point.push_back(seg[i].s);
		point.push_back(seg[i].t);
		range(j,i+1,seg.size()){
			if (iSS(seg[i],seg[j]))
				point.push_back( pLL(seg[i],seg[j]));
		}
	}
	sort(point.begin(),point.end(),cmp_x);
	point.erase(unique(point.begin(),point.end(),cmp_x), point.end());

	rep(i,seg.size()){
		vector< pair<D, int> > list;
		rep(j,point.size())
			if (ccw(seg[i].s,seg[i].t, point[j])==MID)
				list.push_back(make_pair(norm(seg[i].s-point[j]), j));
		sort(list.begin(),list.end());
		range(j,1,list.size()){
			int a = list[j-1].second, b = list[j].second;
			graph[a].push_back( {b, abs(point[a]-point[b])} );
			graph[b].push_back( {a, abs(point[a]-point[b])} );
		}
	}
}



// under not verify

// ????????????????????????
/*
vector<L> merge(vector<L> lines) {
	rep(i,lines.size())
		if(lines[i].t < lines[i].s)
			swap(lines[i].s, lines[i].t);
	sort(lines.begin(),lines.end());
	rep(i,lines.size())rep(j,i){
		if (iSS(lines[i],lines[j])&&!iSSs(lines[i],lines[j])){
			if(abs(lines[i].t-lines[j].s) > abs(vec(lines[j])))
				lines[j].t = lines[i].t;
			lines.erase(lines.begin() + i--);
			break;
		}
	}
	return lines;
}
*/

// ???????????£??¨????????°?
// ????§???¢???????????????????????????????????????
VP normalize_polygon(VP pol){
	int n=pol.size();
	rep(i,n){
		P prev=pol[(i+n-1)%n];
		P next=pol[(i+1)%n];
		if(ccw(prev,pol[i],next)==MID)
			pol.erase(pol.begin() + i--);
	}
	return pol;
}


L bisector(P a, P b) {
  P mid=(a+b)*P(0.5,0);
  return L{mid, mid+(b-a)*P(0, pi/2)};
}

VP voronoi_cell(VP pol,VP v, int s) {
  rep(i, v.size()) if(i!=s) pol = convex_cut(pol,bisector(v[s], v[i]));
  return pol;
}

int main(void){
    for(int n; cin >> n, n;){
        VP points(n);
        vector<D> l(n);
        rep(i, n) points[i] = input(), cin >> l[i];

        D lb = 0.0, ub = 310;
        rep(loop, 100){
            D mid = (lb + ub) / 2.0;

            bool ok = false;
            [&]
            {
                VC circles(n);
                rep(i, n){
                    D r2 = pow(l[i], 2) - pow(mid, 2);
                    if(r2 < -eps) return;
                    circles[i] = { points[i], sq(r2) };
                }

                VP ps;
                rep(i, n){
                    ps.push_back(circles[i].c);

                    range(j, i + 1, n){
                        VP ret = pCC(circles[i], circles[j]);
                        ps.insert(end(ps), begin(ret), end(ret));
                    }
                }

                for(auto & p : ps){
                    bool all_in = true;
                    [&]{
                        rep(i, n){
                            if(not (abs(p - circles[i].c) <= circles[i].r + eps)){
                                all_in = false;
                                return;
                            }
                        }
                    }();

                    if(all_in){
                        ok = true;
                        return;
                    }
                }
            }();

            if(ok){
                lb = mid;
            }
            else {
                ub = mid;
            }
        }

        cout.precision(12);
        cout << lb << endl;
    }


    return 0;
}