Problem: A long time ago in a galaxy, far, far away, there were N spheres with various radii. Spheres were mirrors, that is, they had reflective surfaces . . . .

You are standing at the origin of the galaxy (0, 0, 0), and emit a laser ray to the direction (u,v, w). The ray travels in a straight line.

When the laser ray from I hits the surface of a sphere at Q, let N be a point outside of the sphere on the line connecting the sphere center and Q. The reflected ray goes to the direction towards R that satisfies the following conditions: (1) R is on the plane formed by the three points I, Q and N , (2) ∠ IQN = ∠ NQR, as shown in Figure 1.

<image>
---
Figure 1: Laser ray reflection

After it is reflected several times, finally it goes beyond our observation. Your mission is to write a program that identifies the last reflection point.



Input

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


N
u v w
x1 y1 z1 r1
.
.
.
xN yN zN rN


The first line of a dataset contains a positive integer N which is the number of spheres. The next line contains three integers u, v and w separated by single spaces, where (u, v, w) is the direction of the laser ray initially emitted from the origin.

Each of the following N lines contains four integers separated by single spaces. The i-th line corresponds to the i-th sphere, and the numbers represent the center position (xi, yi, zi ) and the radius ri .

N, u, v, w, xi, yi, zi and ri satisfy the following conditions.

1 ≤ N ≤ 100
−100 ≤ u, v, w ≤ 100
−100 ≤ xi, yi, zi ≤ 100
5 ≤ ri ≤ 30
u2 + v2 + w2 > 0


You can assume that the distance between the surfaces of any two spheres is no less than 0.1. You can also assume that the origin (0, 0, 0) is located outside of any sphere, and is at least 0.1 distant from the surface of any sphere.

The ray is known to be reflected by the sphere surfaces at least once, and at most five times. You can assume that the angle between the ray and the line connecting the sphere center and the reflection point, which is known as the angle of reflection (i.e. θ in Figure 1), is less than 85 degrees for each point of reflection.

The last dataset is followed by a line containing a single zero.

Output

For each dataset in the input, you should print the x-, y- and z-coordinates of the last reflection point separated by single spaces in a line. No output line should contain extra characters.

No coordinate values in the output should have an error greater than 0.01.

Example

Input

3
-20 -20 -24
100 100 100 30
10 8 3 5
-70 -70 -84 5
4
0 47 84
-23 41 42 8
45 -10 14 19
-5 28 47 12
-27 68 34 14
0


Output

79.0940 79.0940 94.9128
-21.8647 54.9770 34.1761

Solution (in CPP):

Solution:

#include<bits/stdc++.h>
 
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define IINF (INT_MAX)
#define EPS (1e-7)
#define equals(a,b) (fabs((a)-(b))<EPS)
#define MAX 110
 
using namespace std;
 
//テ、ツスツ愿ヲツ按静、ツクツュ Verifyテ」ツ?療」ツ?淌」ツつづ」ツ?ョテ」ツ?ォテ」ツ?ッVerifyテ」ツ?ィテヲツ崢クテ」ツ??」ツ?ヲテ」ツ?づ」ツつ?
 
//Verify AOJ 0115
class Point3d{
public:
  double x,y,z;
 
  Point3d(double x=0,double y=0,double z=0):x(x),y(y),z(z){}
 
  Point3d operator + (const Point3d& a){
    return Point3d(x+a.x,y+a.y,z+a.z);
  }
  Point3d operator - (const Point3d& a){
    return Point3d(x-a.x,y-a.y,z-a.z);
  }
  Point3d operator * (const double& d){
    return Point3d(x*d,y*d,z*d);
  }
  Point3d operator / (const double& d){
    return Point3d(x/d,y/d,z/d);
  }
 
  bool operator < (const Point3d& p)const{
    return !equals(x,p.x)?x<p.x:((!equals(y,p.y))?y<p.y:z<p.z);
  }
 
  bool operator == (const Point3d& p)const{
    return equals(x,p.x) && equals(y,p.y) && equals(z,p.z);
  }
 
};
 
//Verify AOJ 0115
struct Segment3d{
  Point3d p[2];
  Segment3d(Point3d p1=Point3d(),Point3d p2=Point3d()){
    p[0] = p1, p[1] = p2;
  }
  bool operator == (const Segment3d& seg)const{
    return p[0] == seg.p[0] && p[1] == seg.p[1];
  }
};
 
typedef Point3d Vector3d;
typedef Segment3d Line3d;
 
 
 
 
ostream& operator << (ostream& os,const Point3d& p){
  os << "(" << p.x << "," << p.y << "," << p.z << ")";
}
 
ostream& operator << (ostream& os,const Segment3d& seg){
  os << "(" << seg.p[0] << "," << seg.p[1] << ")";
}
 
//Verify AOJ 0115
double dot(const Point3d& a,const Point3d& b){
  return a.x*b.x + a.y*b.y + a.z*b.z;
}
 
//Verify AOJ 0115
Vector3d cross(const Point3d& a,const Point3d& b){
  return Vector3d(a.y*b.z-a.z*b.y,a.z*b.x-a.x*b.z,a.x*b.y-a.y*b.x);
}
 
//Verify AOJ 0115
inline double norm(const Point3d &p){
  return p.x*p.x + p.y*p.y + p.z*p.z;
}
 
//Verify AOJ 0115
inline double abs(const Point3d &p){
  return sqrt(norm(p));
}
 
inline double toRad(double theta){
  return theta * M_PI / 180.0;
}
 
 
 
bool on_line3d(Line3d line,Point3d p){
  return equals(abs(cross(p-line.p[0],line.p[1]-line.p[0])),0);
}
 
bool on_segment3d(Segment3d seg,Point3d p){
  if( !on_line3d(seg,p) ) return false;
  double dist[3] = { abs(seg.p[1]-seg.p[0]), abs(p-seg.p[0]), abs(p-seg.p[1]) };  
  return on_line3d(seg,p) && equals(dist[0],dist[1]+dist[2]);
}
 
//Verify AOJ 0115
bool point_on_the_triangle3d(Point3d tri1,Point3d tri2,Point3d tri3,Point3d p){
 
  //テァツキツ堙・ツ按?、ツクツ甘」ツ?ォpテ」ツ?古」ツ?づ」ツ?」テ」ツ?淌・ツ?エテ・ツ青暗」ツ??、ツクツ嘉ィツァツ津・ツスツ「テ・ツ??」ツ?ィテ」ツ?ソテ」ツ?ェテ」ツ??
  //if( on_segment3d(Segment3d(tri1,tri2),p) ) return true;
  //if( on_segment3d(Segment3d(tri2,tri3),p) ) return true;
  //if( on_segment3d(Segment3d(tri3,tri1),p) ) return true;
 
  Vector3d v1 = tri2 - tri1;
  Vector3d v2 = tri3 - tri2;
  Vector3d v3 = tri1 - tri3;
 
  Vector3d cp[3] = { cross(v1,p-tri1), cross(v2,p-tri2), cross(v3,p-tri3) };
  double d1 = dot(cp[0],cp[1]);
  double d2 = dot(cp[0],cp[2]);
 
  // テァツキツ堙・ツ按?、ツクツ甘」ツ?ォpテ」ツ?古」ツ?づ」ツ?」テ」ツ?淌・ツ?エテ・ツ青?テ、ツクツ嘉ィツァツ津・ツスツ「テ・ツ??」ツ?ィテ」ツ?ッテ」ツ?ソテ」ツ?ェテ」ツ?陛」ツ?ェテ」ツ??
  //if( ( !equals(d1,0.0) && d1 > 0 ) && ( !equals(d2,0.0) && d2 > 0 ) ) return true;
 
  // テァツキツ堙・ツ按?、ツクツ甘」ツ?ォpテ」ツ?古」ツ?づ」ツ?」テ」ツ?淌・ツ?エテ・ツ青?テ、ツクツ嘉ィツァツ津・ツスツ「テ・ツ??」ツ?ィテ」ツ?ソテ」ツ?ェテ」ツ??
  if( ( equals(d1,0.0) || d1 > 0 ) && ( equals(d2,0.0) || d2 > 0 ) ) return true;
  return false;
}
 
inline Point3d rotateX(Point3d p,double rad){
  return Point3d(p.x,p.y*cos(rad)-p.z*sin(rad),p.y*sin(rad)+p.z*cos(rad));
}
 
inline Point3d rorateY(Point3d p,double rad){
  return Point3d(p.x*cos(rad)+p.z*sin(rad),p.y,-p.x*sin(rad)+p.z*cos(rad));
}
 
inline Point3d rorateZ(Point3d p,double rad){
  return Point3d(p.x*cos(rad)-p.y*sin(rad),p.x*sin(rad)+p.y*cos(rad),p.z);
}
 
inline Point3d rotateEuler(Point3d p,double alpha,double beta,double gamma){
  return Point3d( (cos(alpha)*cos(beta)*cos(gamma)-sin(alpha)*sin(gamma)) * p.x + (-cos(alpha)*cos(beta)*sin(gamma)-sin(alpha)*cos(gamma)) * p.y + (cos(alpha)*sin(beta)) * p.z,
		  (sin(alpha)*cos(beta)*cos(gamma)+cos(alpha)*sin(gamma)) * p.x + (-sin(alpha)*cos(beta)*sin(gamma)+cos(alpha)*cos(gamma)) * p.y + (sin(alpha)*sin(beta)) * p.z,
		  (-sin(beta)*cos(gamma)) * p.x + (sin(beta)*sin(gamma)) * p.y + (cos(beta)) * p.z);
}
 
inline Point3d rotateRollPitchYaw(Point3d p,double roll,double pitch,double yaw){
  return Point3d( ( cos(roll) * cos(pitch) ) * p.x + ( cos(roll) * sin(pitch) * sin(yaw) - sin(roll) * cos(yaw) ) * p.y + ( cos(roll) * sin(pitch) * cos(yaw) + sin(roll) * sin(yaw) ) * p.z,
		  ( sin(roll) * cos(pitch) ) * p.x + ( sin(roll) * sin(pitch) * sin(yaw) + cos(roll) * cos(yaw) ) * p.y + ( sin(roll) * sin(pitch) * cos(yaw) - cos(roll) * sin(yaw) ) * p.z,
		  -sin(pitch) * p.x + cos(pitch) * sin(yaw) * p.y + cos(pitch) * cos(yaw) * p.z);
}
 
 
class Plane3d{
public:
  Point3d normal_vector; //テヲツウツ陛ァツキツ堙」ツδ凖」ツつッテ」ツδ暗」ツδォ
  double d; // テ・ツケツウテゥツ敖「テヲツ鳴ケテァツィツ凝・ツシツ?normal_vector.x * x + normal_vector.y * y + normal_vector.z * z + d = 0
 
  Plane3d(Point3d normal_vector=Point3d(),double d=0):normal_vector(normal_vector),d(d){}
  Plane3d(Vector3d a,Vector3d b,Vector3d c){
    Vector3d v1 = b - a;
    Vector3d v2 = c - a;
    Vector3d tmp = cross(v1,v2);
    normal_vector = tmp / abs(tmp);
    set_d(a);
  }
 
  //Verify AOJ 0115
  //テヲツウツ陛ァツキツ堙」ツδ凖」ツつッテ」ツδ暗」ツδォnormal_vectorテ」ツ?ィテ・ツケツウテゥツ敖「テ、ツクツ甘」ツ?ョテッツシツ妥ァツつケテ」ツ?凝」ツつ嬰テ」ツつ津ィツィツ暗ァツョツ療」ツ?凖」ツつ?
  void set_d(Point3d p){
    d = dot(normal_vector,p);
  }
 
  //テ・ツケツウテゥツ敖「テ」ツ?ィテァツつケpテ」ツ?ョティツキツ敕ゥツ崢「テ」ツつ津ヲツアツづ」ツつ?」ツつ?
  double distanceP(Point3d p){
    Point3d a = normal_vector * d;//テ・ツケツウテゥツ敖「テ、ツクツ甘」ツ?ョテゥツ?ゥテ・ツスツ禿」ツ?ェテァツつケテ」ツつ津」ツ?、テ」ツ?湘」ツつ?
    return abs( dot(p-a,normal_vector) );
  }
 
  //テ・ツケツウテゥツ敖「テ、ツクツ甘」ツ?ァテ」ツつづ」ツ?」テ」ツ?ィテ」ツつづァツつケpテ」ツ?ィティツソツ妥」ツ??ァツつケテ」ツつ津ヲツアツづ」ツつ?」ツつ?
  Point3d nearest_point(Point3d p){
    Point3d a = normal_vector * d;
    return p - ( normal_vector * dot(p-a,normal_vector) );
  }
 
  //Verify AOJ 0115
  //テ・ツケツウテゥツ敖「テ」ツ?ィテァツキツ堙・ツ按?」ツ?古、ツコツ、テ・ツキツョテ」ツ?凖」ツつ凝」ツ??
  bool intersectS(Segment3d seg){
    Point3d a = normal_vector * d;
    double res1 = dot(a-seg.p[0],normal_vector);
    double res2 = dot(a-seg.p[1],normal_vector);
    if( res1 > res2 ) swap(res1,res2);
    //cout << res1 << " < " << res2 << endl;
    if( ( equals(res1,0.0) || res1 < 0 ) && ( equals(res2,0.0) || res2 > 0 ) ) return true;
    return false;
  }
 
  //Verify AOJ 0115
  //テ・ツケツウテゥツ敖「テ」ツ?ィテァツキツ堙・ツ按?」ツ?ョテ、ツコツ、テァツつケテ」ツつ津ヲツアツづ」ツつ?」ツつ?
  Point3d crosspointS(Segment3d seg){
    Point3d a = normal_vector * d;
    double dot_p0a = fabs(dot( seg.p[0]-a,normal_vector ));
    double dot_p1a = fabs(dot( seg.p[1]-a,normal_vector ));
    if( equals(dot_p0a+dot_p1a,0) ) return seg.p[0];
    return seg.p[0] + ( seg.p[1] - seg.p[0] ) * ( dot_p0a / ( dot_p0a + dot_p1a ) );
  }
 
};
 
// Verify AOJ 1289
double distanceLP(Line3d line,Point3d p){
  return abs(cross(line.p[1]-line.p[0],p-line.p[0])) / abs(line.p[1]-line.p[0]);
}

// Verify AOJ 1289
double distanceSP(Segment3d seg,Point3d p){
  double res = dot(seg.p[1]-seg.p[0],p-seg.p[0]);
  if( !equals(res,0.0) && res < 0.0 ) return abs( p - seg.p[0] );
  res = dot(seg.p[0]-seg.p[1],p-seg.p[1]);
  if( !equals(res,0.0) && res < 0.0 ) return abs( p - seg.p[1] );
  return distanceLP(seg,p);
}
 
// Verify AOJ 1289
Point3d project(Segment3d seg,Point3d p){
  Vector3d base = seg.p[1] - seg.p[0];
  double t = dot(p-seg.p[0],base) / norm(base);
  return seg.p[0] + base * t;
}
 
// Verify AOJ 1289
Point3d reflect(Segment3d seg,Point3d p){
  return p + (project(seg,p)-p) * 2.0;
}

//Verify AOJ 2081
bool isParallel(Line3d l1,Line3d l2){
  Vector3d A = l1.p[0], B = l1.p[1], C = l2.p[0], D = l2.p[1];
  Vector3d AB = B - A, CD = D - C;
  Vector3d n1 = AB / abs(AB), n2 = CD / abs(CD);
  double tmp = dot(n1,n2);
  tmp = 1 - tmp*tmp;
  return equals(tmp,0.0);
}
 
//Verify AOJ 2081 
//l1,l2テ」ツ?古・ツケツウティツ。ツ古」ツ?ェテヲツ卍づ」ツ?ォテ」ツ?ッテ、ツスツソテァツ板ィテ」ツ?ァテ」ツ?催」ツ?ェテ」ツ??」ツ?ョテ」ツ?ァテヲツウツィテヲツ??
Segment3d nearest_segmentLL(Line3d l1,Line3d l2){
  assert(!isParallel(l1,l2)); // テ・ツケツウティツ。ツ古」ツ?ェテ・ツ?エテ・ツ青暗」ツ?ッテ、ツスツソテァツ板ィテ、ツクツ催・ツ渉ッ
  // l1.p[0] = A, l1.p[1] = B, l2.p[0] = C, l2.p[1] = D
  Vector3d AB = l1.p[1] - l1.p[0];
  Vector3d CD = l2.p[1] - l2.p[0];
  Vector3d AC = l2.p[0] - l1.p[0];
  Vector3d n1 = AB / abs(AB), n2 = CD / abs(CD);
  double d1 = (dot(n1,AC)-dot(n1,n2)*dot(n2,AC)) / (1.0-pow(dot(n1,n2),2));
  double d2 = (dot(n1,n2)*dot(n1,AC)-dot(n2,AC)) / (1.0-pow(dot(n1,n2),2));
  return Segment3d(l1.p[0]+n1*d1,l2.p[0]+n2*d2);
}
 
//Verify AOJ 2081
bool intersectLL(Line3d l1,Line3d l2){
  Vector3d A = l1.p[0], B = l1.p[1], C = l2.p[0], D = l2.p[1];
 
  //テ」ツ?敕」ツつづ」ツ?敕」ツつＭ1,l2テ」ツ?古ァツ崢エテァツキツ堙」ツ?佚」ツつε」ツ?ェテ」ツ??
  if( equals(abs(B-A),0.0) || equals(abs(D-C),0.0) ){
    /*
      テ」ツ?禿」ツ?ョテ・ツ?エテ・ツ青暗」ツ?ッテヲツウツィテヲツ??
      テ」ツ?敕」ツつづ」ツ?敕」ツつづ、ツクツ偲」ツ?暗」ツつ嘉」ツつ古」ツ?淌ァツキツ堙・ツ按?」ツ?古ァツキツ堙・ツ按?」ツ?ォテ」ツ?ェテ」ツ?」テ」ツ?ヲテ」ツ??」ツ?ェテ」ツ??」ツ?ョテ」ツ?ァテ」ツ??、ツコツ、テ・ツキツョテ」ツ?凖」ツつ凝」ツ?凝」ツ?ゥテ」ツ??」ツ?凝」ツ?ッテ・ツ按、テ・ツョツ堙」ツ?ァテ」ツ?催」ツ?ェテ」ツ??
    */
    return false;
  }
 
  Vector3d AB = B - A, CD = D - C;
  Vector3d n1 = AB / abs(AB), n2 = CD / abs(CD);
  double tmp = dot(n1,n2);
  tmp = 1 - tmp*tmp;
 
  if( equals(tmp,0.0) ) return 0; // テァツ崢エテァツキツ堙」ツ?古・ツケツウティツ。ツ?
 
  Segment3d ns = nearest_segmentLL(l1,l2);
  if( ns.p[0] == ns.p[1] ) return true;
  return false;
}

bool intersectSS(Segment3d seg1,Segment3d seg2){
  if( isParallel(seg1,seg2) ) return false;
  Segment3d seg = nearest_segmentLL(seg1,seg2);
  if( !( seg.p[0] == seg.p[1] ) ) return false;
  Point3d cp = seg.p[1];
  return on_segment3d(seg1,cp) && on_segment3d(seg2,cp);
}


int N;
Segment3d ururu_beam;
Point3d Circle[MAX];
double R[MAX];

inline void Input3d(Point3d &p){ cin >> p.x >> p.y >> p.z; }

inline void compute(){
  int skip = -1;
  bool update = true;
  while(update){
    update = false;
    Point3d tmp_p0,tmp_p1;
    int tmp_skip = -1;
    double tmp_dist = IINF;
    Vector3d vect = ( ururu_beam.p[1] - ururu_beam.p[0] ) / abs( ururu_beam.p[1] - ururu_beam.p[0] );
    Vector3d rvect = ( ururu_beam.p[0] - ururu_beam.p[1] ) / abs( ururu_beam.p[0] - ururu_beam.p[1] );
    ururu_beam.p[1] = ururu_beam.p[0] + vect * 500;
    rep(i,N){
      if( i == skip ) continue;

      double dist = distanceSP(ururu_beam,Circle[i]);
      if( !equals(dist,R[i]) && dist > R[i] ) continue;

      Point3d on_seg = project(ururu_beam,Circle[i]);

      dist = sqrt(pow(R[i],2.0)-norm(on_seg-Circle[i]));
      double x = R[i] * R[i] - norm(on_seg-Circle[i]);
      if( x == 0 ) dist = 0;
      else if( x < 0 ) continue;

      Point3d cp = on_seg + rvect * dist;
      Line3d line = Line3d(Circle[i],cp);

      dist = abs(ururu_beam.p[0]-cp);
      if( tmp_dist > dist ){
        tmp_p0 = cp, tmp_p1 = reflect(line,ururu_beam.p[0]);
        tmp_dist = dist;
        tmp_skip = i;
      }
      update = true;
    }
    if( update ){
      ururu_beam = Segment3d(tmp_p0,tmp_p1);
      skip = tmp_skip;
    }
  }
  printf("%.4f %.4f %.4f\n",ururu_beam.p[0].x,ururu_beam.p[0].y,ururu_beam.p[0].z);
}

int main(){
  while( cin >> N, N ){
    ururu_beam.p[0] = Point3d(0,0,0);
    Input3d(ururu_beam.p[1]);
    rep(i,N){
      Input3d(Circle[i]);
      cin >> R[i];
    }
    compute();
  }
  return 0;
}