H - Rings

Problem Statement

There are two circles with radius 1 in 3D space. Please check two circles are connected as chained rings.

Input

The input is formatted as follows.


{c_x}_1 {c_y}_1 {c_z}_1
{v_x}_{1,1} {v_y}_{1,1} {v_z}_{1,1} {v_x}_{1,2} {v_y}_{1,2} {v_z}_{1,2}
{c_x}_2 {c_y}_2 {c_z}_2
{v_x}_{2,1} {v_y}_{2,1} {v_z}_{2,1} {v_x}_{2,2} {v_y}_{2,2} {v_z}_{2,2}


First line contains three real numbers(-3 \leq {c_x}_i, {c_y}_i, {c_z}_i \leq 3). It shows a circle's center position. Second line contains six real numbers(-1 \leq {v_x}_{i,j}, {v_y}_{i,j}, {v_z}_{i,j} \leq 1). A unit vector ({v_x}_{1,1}, {v_y}_{1,1}, {v_z}_{1,1}) is directed to the circumference of the circle from center of the circle. The other unit vector ({v_x}_{1,2}, {v_y}_{1,2}, {v_z}_{1,2}) is also directed to the circumference of the circle from center of the circle. These two vectors are orthogonalized. Third and fourth lines show the other circle information in the same way of first and second lines. There are no cases that two circles touch.

Output

If two circles are connected as chained rings, you should print "YES". The other case, you should print "NO". (quotes for clarity)

Sample Input 1


0.0 0.0 0.0
1.0 0.0 0.0 0.0 1.0 0.0
1.0 0.0 0.5
1.0 0.0 0.0 0.0 0.0 1.0


Output for the Sample Input 1


YES


Sample Input 2


0.0 0.0 0.0
1.0 0.0 0.0 0.0 1.0 0.0
0.0 3.0 0.0
0.0 1.0 0.0 -1.0 0.0 0.0


Output for the Sample Input 2


NO


Sample Input 3


1.2 2.3 -0.5
1.0 0.0 0.0 0.0 1.0 0.0
1.1 2.3 -0.4
1.0 0.0 0.0 0.0 0.70710678 0.70710678


Output for the Sample Input 3


YES


Sample Input 4


1.2 2.3 -0.5
1.0 0.0 0.0 0.0 1.0 0.0
1.1 2.7 -0.1
1.0 0.0 0.0 0.0 0.70710678 0.70710678


Output for the Sample Input 4


NO






Example

Input

0.0 0.0 0.0
1.0 0.0 0.0 0.0 1.0 0.0
1.0 0.0 0.5
1.0 0.0 0.0 0.0 0.0 1.0


Output

YES
#include<bits/stdc++.h>
using namespace std;


const double EPS = 1e-9;

struct P3{
  double x,y,z;
  P3(double x,double y, double z):x(x),y(y),z(z) {}
  P3 operator + (const P3 &a) const{ return (P3){x+a.x, y+a.y, z+a.z}; }
  P3 operator - (const P3 &a) const{ return (P3){x-a.x, y-a.y, z-a.z}; }
  P3 operator / (double c) const{ return (P3){x/c, y/c, z/c}; }

};
P3 operator * (double c, const P3 &a){ return (P3){c * a.x, c * a.y, c * a.z}; }
P3 operator * (const P3 &a, double c){ return (P3){c * a.x, c * a.y, c * a.z}; }
//???????????°????????¨
ostream& operator<<(ostream& os,const P3& p) {
  os << "(" << p.x << "," <<p.y << "," << p.z << ")";
  return os;
}


struct L3{
  P3 a,b;
  L3(P3 a,P3 b):a(a),b(b){}
};

struct Plane{
  P3 p,v1,v2;
  Plane(P3 p,P3 v1,P3 v2):p(p),v1(v1),v2(v2) {}
};

struct C3{
  Plane p;
  double r;
};

double norm(P3 a){ return a.x*a.x + a.y*a.y + a.z*a.z; }
double abs(P3 a){ return sqrt(norm(a)); }
double dot(P3 a, P3 b){ return a.x*b.x+ a.y*b.y + a.z*b.z; }
P3 cross(P3 a, P3 b){
  return (P3){a.y*b.z - a.z*b.y, a.z*b.x - a.x*b.z, a.x*b.y - a.y*b.x};
}

// ????????¨???????????¢
double distLP(L3 S, P3 p){
  double a = dot(S.b-S.a, S.b-S.a);
  double b = dot(S.b-S.a, S.a- p );
  double c = dot(S.a- p , S.a- p );
  double t = -b / a;
  return a * t * t + 2 * b * t + c;
}

//???????????´??????????°???±
P3 proj( L3 l, P3 p ){
  P3 v1 = p-l.a, v2 = l.b-l.a;
  return (dot(v1,v2)/norm(v2)) * v2 + l.a;
}

//??????????????¢???????°???±????¬???????????????¢????????????
double projLen( P3 x, Plane p ){
  P3 a = cross( p.v1, p.v2 );
  P3 b = x-p.p;
  return dot(a,b)/abs(a);
}

//??????????????¢???????°???±
P3 proj( P3 x, Plane p ){
  P3 a = cross( p.v1, p.v2 );
  P3 b = x - p.p;
  return x - a * (dot(a,b)/norm(a));
}

//?????????????????¢???????°???±
L3 proj( L3 s, Plane p ){
  return L3( proj( s.a, p ), proj( s.b, p ) );
}

//??´?????¨?????¢????????????
bool isParallel( L3 a, Plane b ){
  return abs(norm(a.a-proj( a.a, b )) - norm(a.b-proj(a.b,b))) < EPS;
}

//?????¢??¨?????¢????????????
bool isParallel( Plane a, Plane b ){
  return isParallel(L3(a.p,a.p+a.v1),b) && isParallel(L3(a.p,a.p+a.v2),b);
}

/*
vector<P3> closestPoint( L3 s1, L3 s2 ){
  P3 n1 = s1.b-s1.a, n2 = s2.b-s2.a;
  P3 ac = s1.b-s2.a;
  double d1 = ( dot( n1, ac ) - dot( n1, n2 ) * dot( n2, ac ) ) / ( 1.0 - dot(n1,n2)*dot(n1,n2) );
  double d2 = ( dot( n1, n2 ) * dot( n1, ac ) - dot( n2, ac ) ) / ( 1.0 - dot(n1,n2)*dot(n1,n2) );
  P3 p1 = s1.a + d1 * n1;
  P3 p2 = s2.a + d2 * n2;
  if( abs(p1-p2) < EPS ) return vector<P3>(1,p1);
  vector<P3> ret; ret.push_back( p1 ); ret.push_back( p2 );
  return ret;
}
*/

//??´?????¨?????¢?????????( isParallel???????????????????????§??????????????£??? )
P3 crossPoint( L3 l, Plane p ){
  double y = projLen( l.b, p );
  double x = projLen( l.a, p )-y;
  return l.a + (l.b-l.a) / x * (x+y);
}

//?????¢??¨?????¢??§?????????????????¨????????§????????´???(?????¨???????????´???(0,0,0)-(0,0,0))
L3 plane_cut( Plane a, Plane b ){
  L3 x = L3( a.p, a.p + a.v1 );
  L3 y = L3( a.p, a.p + a.v2 );
  if( isParallel( x, b ) ) {
    if( isParallel( y, b ) ) return L3(P3(0,0,0),P3(0,0,0));
    L3 y2 = L3( x.b, x.b + a.v2 );
    return L3( crossPoint( y, b ), crossPoint( y2, b ) );
  } else {
    L3 x2 = L3( y.b, y.b + a.v1 );
    return L3( crossPoint( x, b ), crossPoint( x2, b ) );
  }  
}

//?????¨??´???????????¢???r??§??????????????????
vector<P3> touchLP( L3 S, P3 p, double r ){
  P3 tp = proj( S, p );
  double k = abs(tp-p);
  if( k-EPS > r ) return vector<P3>();//????????´?????????
  if( k+EPS > r ) return vector<P3>(1,tp);
  vector<P3> ret;
  double x = sqrt( r*r - k*k );
  P3 v = S.a - tp;
  ret.push_back( P3( tp + (v/abs(v) * x) ) );
  ret.push_back( P3( tp - (v/abs(v) * x) ) );
  return ret;
}

// P3 p ??? ???c?????¨???????????¢??????????????¨???????¨???????????????¨??????
bool inCircle( C3 c, P3 p ){
  if( abs( c.p.p - p ) < c.r+EPS ) return true;
  return false;               
}


bool Rings( C3 c1, C3 c2 ){
  //?????¢?????????????????´???
  L3 l = plane_cut( c1.p, c2.p );
  vector<P3> ps = touchLP( l, c2.p.p, c2.r );
  if( ps.size()==2 ){
    bool f1 = inCircle( c1, ps[0] );
    bool f2 = inCircle( c1, ps[1] );
    return f1 == !f2 && f2 == !f1;
  }
  return false;
}

int main(){
  double cx,cy,cz;
  double vx,vy,vz,vx2,vy2,vz2;
  cin >> cx >> cy >> cz;
  cin >> vx >> vy >> vz >> vx2 >> vy2 >> vz2;
  Plane sp1 = (Plane){ P3(cx,cy,cz), P3(vx,vy,vz), P3(vx2,vy2,vz2) };
  cin >> cx >> cy >> cz;
  cin >> vx >> vy >> vz >> vx2 >> vy2 >> vz2;
  Plane sp2 = (Plane){ P3(cx,cy,cz), P3(vx,vy,vz), P3(vx2,vy2,vz2) };

  C3 c1 = (C3){sp1,1.0};
  C3 c2 = (C3){sp2,1.0};

  if( Rings(c1,c2) ) cout << "YES" << endl;
  else cout << "NO" << endl;
}