#include<bits/stdc++.h>
using namespace std;
const double eps = 0.0000000001;
pair<double,int> Pair;

bool eq(double a,double b){
  return ( fabs(a-b) < eps );
}

struct Point{
  double x,y,z;
  
  Point operator + (Point p){
    return (Point){x+p.x,y+p.y,z+p.z};
  }
  
  Point operator * (double k){
    return (Point){x*k,y*k,z*k};
  }
};
typedef Point Vector;


void pr(Point p){
  printf("%.5f %.5f %.5f\n",p.x,p.y,p.z);
}


double abs(Point p){
  return sqrt( p.x*p.x + p.y*p.y + p.z*p.z );
}

Point cross(Point a,Point b){
  double nx=a.y*b.z-b.y*a.z;
  double ny=a.z*b.x-b.z*a.x;
  double nz=a.x*b.y-b.x*a.y;
  return (Point){nx,ny,nz};
}

bool eq(Point a,Point b){
  return ( eq(a.x,b.x) && eq(a.y,b.y) && eq(a.z,b.z) );
}

struct Segment{
  Point p, v;
};
typedef Segment Line;

struct Plane{
  Point p, v1, v2;
};

bool isParallel(Vector a,Vector b){
  return ( abs( cross(a,b) ) < eps );
}

bool isParallel(Plane a,Plane b){
  Vector cra=cross(a.v1,a.v2);
  Vector crb=cross(b.v1,b.v2);
  return  isParallel(cra,crb); 
}

Line getLine(Plane a,double A,double B,double C){
  Point p=a.p;
  Vector v=a.v1;
  if( eq(0,A) ){
    C/=B;
    p=p+(a.v2*C);
    v=a.v1;
  }else if(eq(0,B)){
    C/=A;
    p=p+(a.v1*C);
    v=a.v2;
  }else{
    p=p+(a.v1*(C/A));
    v=a.v1*(-B/A);
    v=v+a.v2;
  }
  return (Line){p,v};
}

void printvec( vector< vector< double> > G){
  for(int i=0;i<3;i++){
    for(int j=0;j<5;j++){
      G[i][j]+=0.0;
      printf("%.8f ",G[i][j]);
    }
    cout<<endl;
  }cout<<endl;  
}

Line getCrossLine(Plane a,Plane b){
  assert( !isParallel(a,b) );
  vector< vector<double> > G( 3, vector<double>(5) );
  //0=A,1=B,2=C,3=D
  G[0][0]=a.v1.x;
  G[0][1]=a.v2.x;
  G[0][2]=-b.v1.x;
  G[0][3]=-b.v2.x;
  G[0][4]=-(a.p.x-b.p.x);
  
  G[1][0]=a.v1.y;
  G[1][1]=a.v2.y;
  G[1][2]=-b.v1.y;
  G[1][3]=-b.v2.y;
  G[1][4]=-(a.p.y-b.p.y);

  G[2][0]=a.v1.z;
  G[2][1]=a.v2.z;
  G[2][2]=-b.v1.z;
  G[2][3]=-b.v2.z;
  G[2][4]=-(a.p.z-b.p.z);

  bool flg[3]={};
  for(int i=0;i<4;i++){
    int pivot=-1;
    double maxm=-1;
    for(int j=0;j<3;j++){
      if(flg[j])continue;
      if(eq(G[j][i],0))continue;
      if( maxm < fabs(G[j][i]) ){
        pivot=j;
        maxm=fabs(G[j][i]);
      }
    }
    if(pivot==-1)continue;

    flg[pivot]=true;
    double k=G[pivot][i];
    for(int j=0;j<5;j++)G[pivot][j]/=k;
    for(int j=0;j<3;j++){
      if(j==pivot)continue;
      double rate=G[j][i];
      for(int k=0;k<5;k++){
        G[j][k]-=G[pivot][k]*rate;
      }
    }
  }
  
  for(int i=0;i<3;i++){
    bool flg=false;
    for(int j=0;j<4;j++)
      if( !eq(G[i][j],0) )flg=true;
    if(!flg)continue;
    
    if( eq(G[i][0],0) && eq(G[i][1],0) ){
      return getLine(b,G[i][2],G[i][3],G[i][4]);
    }

    if( eq(G[i][2],0) && eq(G[i][3],0) ){
      return getLine(a,G[i][0],G[i][1],G[i][4]);
    }
  }
  
  return (Line){(Point){0,0,0},(Point){0,0,0}};
}

double getTime(Line a,Point b){
  b.x -= a.p.x;
  b.y -= a.p.y;
  b.z -= a.p.z;
  if( !eq(a.v.x,0) )return b.x/a.v.x;
  if( !eq(a.v.y,0) )return b.y/a.v.y;
  if( !eq(a.v.z,0) )return b.z/a.v.z;
  return 1e30;
}

vector<Point> getCrossPoint(Line a,Point b,double r){
  vector<Point> res;
  double X=a.p.x-b.x;
  double Y=a.p.y-b.y;
  double Z=a.p.z-b.z;
  double A=(a.v.x*a.v.x+a.v.y*a.v.y+a.v.z*a.v.z);
  double B=(X*a.v.x+Y*a.v.y+Z*a.v.z)*2.0;
  double C=X*X+Y*Y+Z*Z-r*r;
  double K=B*B-4.0*A*C;
  if( K < -eps )return res;
  if( eq(K,0) )K=0;
  double t =  (-B + sqrt(B*B-4.0*A*C)) / (2.0*A);
  double t2 =  (-B - sqrt(B*B-4.0*A*C)) / (2.0*A);
  res.push_back(a.p+a.v*t);
  if(!eq(t,t2))res.push_back(a.p+a.v*t2);
  return res;
}

void scan(Point &p){
  cin>>p.x>>p.y>>p.z;
}


string solve(Plane a,Plane b){
  if( isParallel(a,b) )return "NO";
  Line l=getCrossLine(a,b);
  vector<Point> Ga=getCrossPoint(l,a.p,1);
  vector<Point> Gb=getCrossPoint(l,b.p,1);
  if(min(Ga.size(),Gb.size())<2)return "NO";
  
  vector< pair<double,int> > g;
  pair<double,int> pa;
  
  for(int i=0;i<2;i++){
    pa.first=getTime(l,Ga[i]);
    pa.second=0;
    g.push_back(pa);
    
    pa.first=getTime(l,Gb[i]);
    pa.second=1;
    g.push_back(pa);
  }

  sort(g.begin(),g.end());
  for(int i=1;i<4;i++){
    if( eq(g[i].first,g[i-1].first))return "NO";
    if( g[i].second == g[i-1].second)return "NO";
  }
  return "YES";
}

int main(){
  Plane a,b;
  scan(a.p);
  scan(a.v1);
  scan(a.v2);
  scan(b.p);
  scan(b.v1);
  scan(b.v2);
  cout<<solve(a,b)<<endl;
  return 0;
}
### Prompt

Your task is to create a CPP solution to the following problem:

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

### Response

```cpp
#include<bits/stdc++.h>
using namespace std;
const double eps = 0.0000000001;
pair<double,int> Pair;

bool eq(double a,double b){
  return ( fabs(a-b) < eps );
}

struct Point{
  double x,y,z;
  
  Point operator + (Point p){
    return (Point){x+p.x,y+p.y,z+p.z};
  }
  
  Point operator * (double k){
    return (Point){x*k,y*k,z*k};
  }
};
typedef Point Vector;


void pr(Point p){
  printf("%.5f %.5f %.5f\n",p.x,p.y,p.z);
}


double abs(Point p){
  return sqrt( p.x*p.x + p.y*p.y + p.z*p.z );
}

Point cross(Point a,Point b){
  double nx=a.y*b.z-b.y*a.z;
  double ny=a.z*b.x-b.z*a.x;
  double nz=a.x*b.y-b.x*a.y;
  return (Point){nx,ny,nz};
}

bool eq(Point a,Point b){
  return ( eq(a.x,b.x) && eq(a.y,b.y) && eq(a.z,b.z) );
}

struct Segment{
  Point p, v;
};
typedef Segment Line;

struct Plane{
  Point p, v1, v2;
};

bool isParallel(Vector a,Vector b){
  return ( abs( cross(a,b) ) < eps );
}

bool isParallel(Plane a,Plane b){
  Vector cra=cross(a.v1,a.v2);
  Vector crb=cross(b.v1,b.v2);
  return  isParallel(cra,crb); 
}

Line getLine(Plane a,double A,double B,double C){
  Point p=a.p;
  Vector v=a.v1;
  if( eq(0,A) ){
    C/=B;
    p=p+(a.v2*C);
    v=a.v1;
  }else if(eq(0,B)){
    C/=A;
    p=p+(a.v1*C);
    v=a.v2;
  }else{
    p=p+(a.v1*(C/A));
    v=a.v1*(-B/A);
    v=v+a.v2;
  }
  return (Line){p,v};
}

void printvec( vector< vector< double> > G){
  for(int i=0;i<3;i++){
    for(int j=0;j<5;j++){
      G[i][j]+=0.0;
      printf("%.8f ",G[i][j]);
    }
    cout<<endl;
  }cout<<endl;  
}

Line getCrossLine(Plane a,Plane b){
  assert( !isParallel(a,b) );
  vector< vector<double> > G( 3, vector<double>(5) );
  //0=A,1=B,2=C,3=D
  G[0][0]=a.v1.x;
  G[0][1]=a.v2.x;
  G[0][2]=-b.v1.x;
  G[0][3]=-b.v2.x;
  G[0][4]=-(a.p.x-b.p.x);
  
  G[1][0]=a.v1.y;
  G[1][1]=a.v2.y;
  G[1][2]=-b.v1.y;
  G[1][3]=-b.v2.y;
  G[1][4]=-(a.p.y-b.p.y);

  G[2][0]=a.v1.z;
  G[2][1]=a.v2.z;
  G[2][2]=-b.v1.z;
  G[2][3]=-b.v2.z;
  G[2][4]=-(a.p.z-b.p.z);

  bool flg[3]={};
  for(int i=0;i<4;i++){
    int pivot=-1;
    double maxm=-1;
    for(int j=0;j<3;j++){
      if(flg[j])continue;
      if(eq(G[j][i],0))continue;
      if( maxm < fabs(G[j][i]) ){
        pivot=j;
        maxm=fabs(G[j][i]);
      }
    }
    if(pivot==-1)continue;

    flg[pivot]=true;
    double k=G[pivot][i];
    for(int j=0;j<5;j++)G[pivot][j]/=k;
    for(int j=0;j<3;j++){
      if(j==pivot)continue;
      double rate=G[j][i];
      for(int k=0;k<5;k++){
        G[j][k]-=G[pivot][k]*rate;
      }
    }
  }
  
  for(int i=0;i<3;i++){
    bool flg=false;
    for(int j=0;j<4;j++)
      if( !eq(G[i][j],0) )flg=true;
    if(!flg)continue;
    
    if( eq(G[i][0],0) && eq(G[i][1],0) ){
      return getLine(b,G[i][2],G[i][3],G[i][4]);
    }

    if( eq(G[i][2],0) && eq(G[i][3],0) ){
      return getLine(a,G[i][0],G[i][1],G[i][4]);
    }
  }
  
  return (Line){(Point){0,0,0},(Point){0,0,0}};
}

double getTime(Line a,Point b){
  b.x -= a.p.x;
  b.y -= a.p.y;
  b.z -= a.p.z;
  if( !eq(a.v.x,0) )return b.x/a.v.x;
  if( !eq(a.v.y,0) )return b.y/a.v.y;
  if( !eq(a.v.z,0) )return b.z/a.v.z;
  return 1e30;
}

vector<Point> getCrossPoint(Line a,Point b,double r){
  vector<Point> res;
  double X=a.p.x-b.x;
  double Y=a.p.y-b.y;
  double Z=a.p.z-b.z;
  double A=(a.v.x*a.v.x+a.v.y*a.v.y+a.v.z*a.v.z);
  double B=(X*a.v.x+Y*a.v.y+Z*a.v.z)*2.0;
  double C=X*X+Y*Y+Z*Z-r*r;
  double K=B*B-4.0*A*C;
  if( K < -eps )return res;
  if( eq(K,0) )K=0;
  double t =  (-B + sqrt(B*B-4.0*A*C)) / (2.0*A);
  double t2 =  (-B - sqrt(B*B-4.0*A*C)) / (2.0*A);
  res.push_back(a.p+a.v*t);
  if(!eq(t,t2))res.push_back(a.p+a.v*t2);
  return res;
}

void scan(Point &p){
  cin>>p.x>>p.y>>p.z;
}


string solve(Plane a,Plane b){
  if( isParallel(a,b) )return "NO";
  Line l=getCrossLine(a,b);
  vector<Point> Ga=getCrossPoint(l,a.p,1);
  vector<Point> Gb=getCrossPoint(l,b.p,1);
  if(min(Ga.size(),Gb.size())<2)return "NO";
  
  vector< pair<double,int> > g;
  pair<double,int> pa;
  
  for(int i=0;i<2;i++){
    pa.first=getTime(l,Ga[i]);
    pa.second=0;
    g.push_back(pa);
    
    pa.first=getTime(l,Gb[i]);
    pa.second=1;
    g.push_back(pa);
  }

  sort(g.begin(),g.end());
  for(int i=1;i<4;i++){
    if( eq(g[i].first,g[i-1].first))return "NO";
    if( g[i].second == g[i-1].second)return "NO";
  }
  return "YES";
}

int main(){
  Plane a,b;
  scan(a.p);
  scan(a.v1);
  scan(a.v2);
  scan(b.p);
  scan(b.v1);
  scan(b.v2);
  cout<<solve(a,b)<<endl;
  return 0;
}
```