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>
using namespace std;
#define REP(i,n) for(long long i=0;i<n;i++)
#define REP1(i,n) for(long long i=1;i<=n;i++)
#define REP2D(i,j,h,w) for(long long i=0;i<h;i++) for(long long j=0;j<w;j++)
#define REP2D1(i,j,h,w) for(long long i=1;i<=h;i++) for(long long j=1;j<=w;j++)
#define PER(i,n) for(long long i=((n)-1);i>=0;i--)
#define PER1(i,n) for(long long i=(n);i>0;i--)
#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define FORE(i,a,b) for(long long i=(a);i<=(b);i++)
#define ITE(arr) for(auto ite=(arr).begin();ite!=(arr).end();++ite)
#define ALL(a) (a.begin()),(a.end())
#define RANGE(a) (a),(a+sizeof(a))
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define YNPRT(b) cout<<((b)?"Yes":"No")<<endl
#define REV(arr) reverse(ALL(arr))
#define PRT(a) cout<<a<<endl;
#define PRTLST(arr,num) REP(_i,num) cout<<_i<<" - "<<arr[_i]<<endl;
#define PRTLST2(arr2,d1,d2) REP(_i,d1) REP(_j,d2) cout<<_i<<","<<_j<<" : "<<arr2[_i][_j]<<endl;
#define PRTLST2D(arr2,d1,d2) do{cout<<"L\t";REP(_i,d2) cout<<_i<<"\t"; cout<<endl; REP(_i,d1){cout<<_i<<"\t";REP(_j,d2){cout<<arr2[_i][_j]<<"\t";}cout<<endl;}}while(0);
#define MIN(target,v1) (target)=min(target,v1)
#define MAX(target,v1) (target)=max(target,v1) 
#define P1 first
#define P2 second
#define PB push_back
#define UB upper_bound
#define LB lower_bound

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int INF_INT = 2147483647;
const ll INF_LL = 9223372036854775807LL;
const ull INF_ULL = 18446744073709551615Ull;
const ll P = 92540646808111039LL;
const int Move[4][2] = {-1,0,0,1,1,0,0,-1};
const int Move_[8][2] = {-1,0,-1,-1,0,1,1,1,1,0,1,-1,0,-1,-1,-1};
template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p) {os<<"( "<<p.P1<<" , "<<p.P2<<" )";return os;}
template<typename T>
ostream& operator<<(ostream& os,const vector<T>& v) {ITE(v) os << (ite-v.begin()) << " : " << *ite <<endl;return os;}
template<typename T>
ostream& operator<<(ostream& os,const set<T>& v) {os<<" { ";ITE(v) {os<<*ite;if(ite!=--v.end()){os<<" , ";}} os<<" } ";return os;}
template<typename T1,typename T2>
ostream& operator<<(ostream& os,const map<T1,T2>& m) {ITE(m) {os<<ite->P1<<"\t\t|->\t\t"<<ite->P2<<endl;} return os;}

//---------------------
#define MAXN 11
//---------------------

int n;
double x[MAXN],y[MAXN],l[MAXN];
double retl=0;

struct Matrix{
	double m[3][3];
	Matrix(){ZERO(m);}
	void init(){ZERO(m);}
	void unit(){ZERO(m);m[0][0]=m[1][1]=m[2][2]=1;}
};

Matrix rot;
Matrix rotinv;

#define PRTVEC(vec) cout<<"Vector : "<<(vec.v[0])<< " , " <<(vec.v[1])<<" , "<<(vec.v[2])<<endl;

struct Vector{
	double v[3];
	Vector(){ZERO(v);}
	Vector(double x,double y,double z){v[0]=x;v[1]=y;v[2]=z;}
	void set(double x, double y, double z){v[0]=x,v[1]=y,v[2]=z;}
	void scale(double k){
		REP(i,3) v[i] *= k;
	}
	void mult(double k){scale(k);}
	double mag(){
		return sqrt(v[0]*v[0]+v[1]*v[1]+v[2]*v[2]);
	}
	void normalize(){
		double len=mag();
		if(len!=0) scale(1/len);
	}
	void sub(const Vector& tar){
		REP(i,3) v[i]-=tar.v[i];
	}
	void plus(const Vector& tar){
		REP(i,3) v[i]+=tar.v[i];
	}
};


Vector multMatrix(const Matrix& mat,const Vector& vec){
	Vector v;
	v.set(mat.m[0][0]*vec.v[0]+mat.m[0][1]*vec.v[1] +mat.m[0][2]*vec.v[2]
	 , mat.m[1][0]*vec.v[0]+mat.m[1][1]*vec.v[1] +mat.m[1][2]*vec.v[2] 
	 , mat.m[2][0]*vec.v[0]+mat.m[2][1]*vec.v[1] +mat.m[2][2]*vec.v[2] );
	return v;
}


Vector offset;

void moveToOrigin(Vector& target){
	target.sub(offset);
	target=multMatrix(rot,target);
}

void moveFromOrigin(Vector& target){
	target=multMatrix(rotinv,target);
	target.plus(offset);
}

void setRotate(double theta){
	rot.unit();
	rotinv.unit();
	theta=-theta;
	rot.m[0][0]=cos(theta);
	rot.m[1][1]=cos(theta);
	rot.m[1][0]=sin(theta);
	rot.m[0][1]=-sin(theta);
	theta=-theta;
	rotinv.m[0][0]=cos(theta);
	rotinv.m[1][1]=cos(theta);
	rotinv.m[1][0]=sin(theta);
	rotinv.m[0][1]=-sin(theta);
}

Vector ropes[MAXN];


Vector LM1(const Vector& A){
	return A;
}

bool isGoodRopes(const Vector& A, const Vector& B){
  	double dx=A.v[0]-B.v[0];
  	double dy=A.v[1]-B.v[1];
	double dist=sqrt(dx*dx+dy*dy);
	double la=A.v[2],lb=B.v[2];
	if(lb>=sqrt(la*la+dist*dist)) return false;
	return true;
}

struct GoodRopes{
  	Vector r1,r2;
  	int id1,id2;
  	Vector sol;
	GoodRopes(int a,int b,const Vector& c){
		r1=ropes[a];r2=ropes[b];sol=c;
		id1=a;id2=b;
	}
};

vector<GoodRopes> goodropes;

Vector LM2(int ida, int idb){
  	Vector A=ropes[ida];
  	Vector B=ropes[idb];
	Vector retvec;
	double la=A.v[2],lb=B.v[2];
	if(!isGoodRopes(A,B) || !isGoodRopes(B,A)){
		if(la<lb) return A;
		return B;
	}
	double dx=A.v[0]-B.v[0];
  	double dy=A.v[1]-B.v[1];
	double dist=sqrt(dx*dx+dy*dy);
	double cosTheta=(la*la+dist*dist-lb*lb)/(2*la*dist);
	double distt=cosTheta*la;
	double t=distt/dist;
	double h=sqrt(la*la-distt*distt);
	retvec.set((1-t)*A.v[0]+t*B.v[0],(1-t)*A.v[1]+t*B.v[1],h);
	goodropes.push_back(GoodRopes(ida,idb,retvec));
	return retvec;
}



Vector LM3(const GoodRopes& gr,const Vector& C){
	if(!isGoodRopes(gr.sol,C)) return gr.sol;
	Vector curSol=gr.sol;
	Vector curC=C;
	Vector direction(gr.r1.v[1]-gr.r2.v[1],-(gr.r1.v[0]-gr.r2.v[0]),double(0));
	setRotate(atan2(direction.v[1],direction.v[0]));
	offset.set(curSol.v[0],curSol.v[1],0);
	moveToOrigin(curSol);moveToOrigin(curC);
	double l3=C.v[2];
	double x3=curC.v[0],y3=curC.v[1];
	double l=gr.sol.v[2];
	double cosTheta=(l3*l3-x3*x3-l*l-y3*y3)/(-2*x3*l);
	double newX=l*cosTheta;
	Vector newSol(newX,0,sqrt(l*l-newX*newX));
	moveFromOrigin(newSol);
	return newSol;
}

bool isSafeSol(const Vector& sol,const Vector& test){
	Vector testrp=test;
	testrp.v[2]=0;
	testrp.sub(sol);
	return testrp.mag()<=test.v[2];
}

bool init(){
  	
  	ZERO(x);ZERO(y);ZERO(l);
  	offset.set(0,0,0);
  	goodropes.clear();
  	retl=0;
	cin>>n;
	if(n<=0) return false;
	REP(i,n) cin>>x[i]>>y[i]>>l[i];
	REP(i,n) ropes[i].set(x[i],y[i],l[i]);
	return true;
}


int main(){
  	while(init()){
  		REP(i,n){
  		  	Vector target=LM1(ropes[i]);
  		  	bool isOK = true;
  			FOR(j,0,n){
  				if(i==j) continue;
  				if(!isSafeSol(target,ropes[j])){
  					isOK=false;
  					break;
  				}
  			}
  			if(isOK) MAX(retl,target.v[2]);
  		}
  		
  		if(n==1) {  		printf("%.6lf\n",retl);continue;}
  		
  		REP(i,n-1){
  			FOR(j,i+1,n){
  				Vector target=LM2(i,j);
  				bool isOK=true;
  				FOR(k,0,n){
  					if(i==k || j==k) continue;
  					if(!isSafeSol(target,ropes[k])){
  						isOK=false;
  						break;
  					}
  				}
  				if(isOK) MAX(retl,target.v[2]);
  			}
  		}
  		
  		if(n==2) {  		printf("%.6lf\n",retl);continue;}
  		
  		ITE(goodropes){
  			REP(i,n){
  				if(i==ite->id1 || i== ite->id2) continue;
  				Vector target=LM3(*ite,ropes[i]);
  				bool isOK=true;
  				REP(j,n){
  					if(j==ite->id1 || j==ite->id2 || j==i) continue;
  					if(!isSafeSol(target,ropes[j])){
  						isOK=false;
  						break;
  					}
  				}
  				if(isOK) {MAX(retl,target.v[2]);}
  			}  
  		}
  		printf("%.6lf\n",retl);
  	}
	return 0;
}