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

double eps = 1e-8, PI = acos(-1);

double Sqrt(double x){
  return (x<0?0:sqrt(x));
}

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

struct Point{
  double x,y,z;
  Point (double a=0,double b=0,double c=0): x(a),y(b),z(c) {}
  Point operator + (const Point &p)const{
    return Point(x+p.x,y+p.y,z+p.z);
  }
  Point operator - (const Point &p)const{
    return Point(x-p.x,y-p.y,z-p.z);
  }
  Point operator * (const double &r)const{
    return Point(x*r,y*r,z*r);
  }
  Point operator / (const double &r)const{
    return Point(x/r,y/r,z/r);
  }
};

typedef Point Vector;

double dot(Point a,Point b){
  return a.x*b.x+a.y*b.y+a.z*b.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);
}

double norm(Point a){
  return dot(a,a);
}

double abs(Point a){
  return sqrt( norm(a) );
}


struct Line{
  Point p,q;
  Line(Point a=Point(),Point b=Point()):p(a),q(b){}
  Point v(){    return q-p;  }
};


struct Plane{
  Point p;
  Vector v0,v1;
  Plane(Point a=Point(),Vector b=Vector(),Vector c=Vector())
    :p(a),v0(b),v1(c){}
};

Point cross(Plane s){
  return cross(s.v0,s.v1);
}

bool isParallel(Vector s,Vector t){
  return eq( 0.0 , abs(cross(s,t)) );
}

bool isParallel(Plane s,Vector t){
  return eq(0,dot(cross(s.v0,s.v1),t));
}

bool isParallel(Plane s,Plane t){
  return isParallel( cross(s.v0,s.v1) , cross(t.v0,t.v1) );
}


double getDistance(Plane s,Point t){
  Vector A=cross(s.v0,s.v1);
  return dot(A,t-s.p)/abs(A);
}

Point getCrossPoint(Plane s,Line t){
  double A=getDistance(s,t.p);
  double B=getDistance(s,t.p+t.v());
  return t.p+t.v()*A/(A-B);
}

Line getCrossLine(Plane s,Plane t){
  Point A;
  if(isParallel(s,t.v0))A=getCrossPoint(s,Line(t.p,t.p+t.v1));
  else A=getCrossPoint(s,Line(t.p,t.p+t.v0));
  return Line(A,A+cross(cross(s),cross(t)));
}

struct Sphere{
  Point p;
  double r;
  Sphere(Point a,double b):p(a),r(b){}
};

vector<Point> getCrossPoint(Sphere s,Line t){
  vector<Point> res;
  Vector a=s.p-t.p;
  Vector b=t.v();
  double base=dot(a,b)/abs(b);
  double hh=norm(cross(a,b))/norm(b);
  if(s.r*s.r+eps < hh )return res;
  double w=Sqrt( s.r*s.r - hh );
  res.push_back(t.p+t.v()/abs(t.v())*(base-w));
  res.push_back(t.p+t.v()/abs(t.v())*(base+w));
  return res;
}

double getTime(Line s,Point t){
  double res= abs(t-s.p)/abs(s.v());
  return (dot(t-s.p,s.v())>0.0?res:-res);
}

string solve(){
  Plane s,t;
  cin>>s.p.x>>s.p.y>>s.p.z;
  cin>>s.v0.x>>s.v0.y>>s.v0.z;
  cin>>s.v1.x>>s.v1.y>>s.v1.z;
  cin>>t.p.x>>t.p.y>>t.p.z;
  cin>>t.v0.x>>t.v0.y>>t.v0.z;
  cin>>t.v1.x>>t.v1.y>>t.v1.z;
  if( isParallel(s,t) )return "NO";
  Line u=getCrossLine(s,t);
  
  vector<Point> A=getCrossPoint(Sphere(s.p,1),u);
  vector<Point> B=getCrossPoint(Sphere(t.p,1),u);
  if(min(A.size(),B.size())<2)return "NO";
  
  if(getTime(u,A[0]) > getTime(u,A[1]))swap(A[0],A[1]);
  if(getTime(u,B[0]) > getTime(u,B[1]))swap(B[0],B[1]);
  
  if(getTime(u,A[0]) < getTime(u,B[0])&&
     getTime(u,B[0]) < getTime(u,A[1])&&
     getTime(u,A[1]) < getTime(u,B[1]))return "YES";

  if(getTime(u,B[0]) < getTime(u,A[0])&&
     getTime(u,A[0]) < getTime(u,B[1])&&
     getTime(u,B[1]) < getTime(u,A[1]))return "YES";

  return "NO";
}


int main(){
  cout<<solve()<<endl;
  return 0;
}
### Prompt

Please formulate 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;

double eps = 1e-8, PI = acos(-1);

double Sqrt(double x){
  return (x<0?0:sqrt(x));
}

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

struct Point{
  double x,y,z;
  Point (double a=0,double b=0,double c=0): x(a),y(b),z(c) {}
  Point operator + (const Point &p)const{
    return Point(x+p.x,y+p.y,z+p.z);
  }
  Point operator - (const Point &p)const{
    return Point(x-p.x,y-p.y,z-p.z);
  }
  Point operator * (const double &r)const{
    return Point(x*r,y*r,z*r);
  }
  Point operator / (const double &r)const{
    return Point(x/r,y/r,z/r);
  }
};

typedef Point Vector;

double dot(Point a,Point b){
  return a.x*b.x+a.y*b.y+a.z*b.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);
}

double norm(Point a){
  return dot(a,a);
}

double abs(Point a){
  return sqrt( norm(a) );
}


struct Line{
  Point p,q;
  Line(Point a=Point(),Point b=Point()):p(a),q(b){}
  Point v(){    return q-p;  }
};


struct Plane{
  Point p;
  Vector v0,v1;
  Plane(Point a=Point(),Vector b=Vector(),Vector c=Vector())
    :p(a),v0(b),v1(c){}
};

Point cross(Plane s){
  return cross(s.v0,s.v1);
}

bool isParallel(Vector s,Vector t){
  return eq( 0.0 , abs(cross(s,t)) );
}

bool isParallel(Plane s,Vector t){
  return eq(0,dot(cross(s.v0,s.v1),t));
}

bool isParallel(Plane s,Plane t){
  return isParallel( cross(s.v0,s.v1) , cross(t.v0,t.v1) );
}


double getDistance(Plane s,Point t){
  Vector A=cross(s.v0,s.v1);
  return dot(A,t-s.p)/abs(A);
}

Point getCrossPoint(Plane s,Line t){
  double A=getDistance(s,t.p);
  double B=getDistance(s,t.p+t.v());
  return t.p+t.v()*A/(A-B);
}

Line getCrossLine(Plane s,Plane t){
  Point A;
  if(isParallel(s,t.v0))A=getCrossPoint(s,Line(t.p,t.p+t.v1));
  else A=getCrossPoint(s,Line(t.p,t.p+t.v0));
  return Line(A,A+cross(cross(s),cross(t)));
}

struct Sphere{
  Point p;
  double r;
  Sphere(Point a,double b):p(a),r(b){}
};

vector<Point> getCrossPoint(Sphere s,Line t){
  vector<Point> res;
  Vector a=s.p-t.p;
  Vector b=t.v();
  double base=dot(a,b)/abs(b);
  double hh=norm(cross(a,b))/norm(b);
  if(s.r*s.r+eps < hh )return res;
  double w=Sqrt( s.r*s.r - hh );
  res.push_back(t.p+t.v()/abs(t.v())*(base-w));
  res.push_back(t.p+t.v()/abs(t.v())*(base+w));
  return res;
}

double getTime(Line s,Point t){
  double res= abs(t-s.p)/abs(s.v());
  return (dot(t-s.p,s.v())>0.0?res:-res);
}

string solve(){
  Plane s,t;
  cin>>s.p.x>>s.p.y>>s.p.z;
  cin>>s.v0.x>>s.v0.y>>s.v0.z;
  cin>>s.v1.x>>s.v1.y>>s.v1.z;
  cin>>t.p.x>>t.p.y>>t.p.z;
  cin>>t.v0.x>>t.v0.y>>t.v0.z;
  cin>>t.v1.x>>t.v1.y>>t.v1.z;
  if( isParallel(s,t) )return "NO";
  Line u=getCrossLine(s,t);
  
  vector<Point> A=getCrossPoint(Sphere(s.p,1),u);
  vector<Point> B=getCrossPoint(Sphere(t.p,1),u);
  if(min(A.size(),B.size())<2)return "NO";
  
  if(getTime(u,A[0]) > getTime(u,A[1]))swap(A[0],A[1]);
  if(getTime(u,B[0]) > getTime(u,B[1]))swap(B[0],B[1]);
  
  if(getTime(u,A[0]) < getTime(u,B[0])&&
     getTime(u,B[0]) < getTime(u,A[1])&&
     getTime(u,A[1]) < getTime(u,B[1]))return "YES";

  if(getTime(u,B[0]) < getTime(u,A[0])&&
     getTime(u,A[0]) < getTime(u,B[1])&&
     getTime(u,B[1]) < getTime(u,A[1]))return "YES";

  return "NO";
}


int main(){
  cout<<solve()<<endl;
  return 0;
}
```