Problem: Find common tangent lines of two circles $c1$ and $c2$.

Constraints

* $-1,000 \leq c1x, c1y, c2x, c2y \leq 1,000$
* $1 \leq c1r, c2r \leq 1,000$
* $c1$ and $c2$ are different

Input

Center coordinates ($cix$, $ciy$) and radii $cir$ of two circles $c1$ are $c2$ are given in the following format.

$c1x \; c1y \; c1r$
$c2x \; c2y \; c2r$

All input values are given in integers.

Output

Print coordinates of the tangent points on circle $c1$ based on the following rules.

* Print the coordinate with smaller $x$ first. In case of a tie, print the coordinate with smaller $y$ first.



The output values should be in a decimal fraction with an error less than 0.00001.

Examples

Input

1 1 1
6 2 2


Output

0.6153846154 1.9230769231
1.0000000000 0.0000000000
1.4183420913 1.9082895434
1.7355040625 0.3224796874


Input

1 2 1
4 2 2


Output

0.6666666667 1.0571909584
0.6666666667 2.9428090416
2.0000000000 2.0000000000


Input

1 2 1
3 2 2


Output

0.5000000000 1.1339745962
0.5000000000 2.8660254038


Input

0 0 1
1 0 2


Output

-1.0000000000 0.0000000000


Input

0 0 1
0 0 2


Output

Solution (in CPP):

Solution:



#include<bits/stdc++.h>

using namespace std;

#define EPS (1e-10)
#define equals(a,b) (fabs((a)-(b))<EPS)
#define PI M_PI

const double inf=1e20;

inline int sign(const double &x){
    if(x>EPS) return 1;
    else if(x<-EPS) return -1;
    return 0;
}

/*   点  */
struct Point{
    double x,y;

    Point(double x=0,double y=0):x(x),y(y){}

    Point operator + (Point p) { return Point(x+p.x,y+p.y); }
    Point operator - (Point p) { return Point(x-p.x,y-p.y); }
    Point operator * (double k) { return Point(k*x,k*y); }
    Point operator / (double k) { return Point(x/k,y/k); }

    //向量的大小
    inline double abs(){ return sqrt(norm()); }
    inline double norm() { return x*x+y*y; }

    bool operator < (const Point & p) const{
        return sign(x-p.x)!=0?sign(x-p.x)<0:sign(y-p.y)<0;
    }

    bool operator == (const Point & p) const {
        return fabs(x-p.x)<EPS&&fabs(y-p.y)<EPS;
    }
};

//两点间的距离
inline double getDistance(Point a,Point b){
    return (a-b).abs();
}

/*   向量  */
typedef Point Vector;

//向量a和b的内积
double dot(Vector a,Vector b){
    return a.x*b.x+a.y*b.y;
}
//向量a和b的外积
double cross(Vector a,Vector b){
    return a.x*b.y-a.y*b.x;
}

/*   线段  */
struct Segment{
    Point p1,p2;
};

//点p在线段s上的投影
Point project(Segment s,Point p){
    Vector base = s.p2-s.p1;
    double r=dot(p-s.p1,base)/base.norm();
    return s.p1+base*r;
}

Point reflect(Segment s,Point p){
    return p+(project(s,p)-p)*2.0;
}

/*   直线  */
typedef Segment Line;

//点到直线的距离
double getDistanceLP(Line l,Point p){
    return abs(cross(l.p2-l.p1,p-l.p1)/(l.p2-l.p1).abs());
}

//点到线段的距离
double getDistanceSP(Segment s,Point p){
    if(dot(s.p2-s.p1,p-s.p1)<0.0) return (p-s.p1).abs();
    if(dot(s.p1-s.p2,p-s.p2)<0.0) return (p-s.p2).abs();
    return getDistanceLP(s,p);
}

//判断p2与向量p1-p0的位置关系

const int COUNTER_CLOCKWISE = -1;   //逆时针
const int CLOCKWISE = 1;            //顺时针
const int ON_SEGMENT = 0;           //在线段上
const int ONLINE_BACK = 2;          //p2在向量p1-p0的反方向延长线上
const int ONLINE_FRONT = -2;        //p2在向量p1-p0的正方向延长线上

int ccw(Point p0,Point p1,Point p2){
    Vector a=p1-p0;
    Vector b=p2-p0;
    if(cross(a,b)>EPS) return COUNTER_CLOCKWISE;
    if(cross(a,b)<-EPS) return CLOCKWISE;
    if(dot(a,b)<-EPS) return ONLINE_BACK;
    if(a.norm()<b.norm()) return ONLINE_FRONT;
    return ON_SEGMENT;
}

//判断线段p1p2与线段p3p4是否相交
bool intersect(Point p1,Point p2,Point p3,Point p4){
    return ( ccw(p1,p2,p3)*ccw(p1,p2,p4)<=0 &&
             ccw(p3,p4,p1)*ccw(p3,p4,p2)<=0 );
}

bool intersect(Segment s1,Segment s2){
    return intersect(s1.p1,s1.p2,s2.p1,s2.p2);
}

//线段与线段的距离
double getDistance(Segment s1,Segment s2){
    if(intersect(s1,s2)) return 0.0;
    return min(min(getDistanceSP(s1,s2.p1),getDistanceSP(s1,s2.p2)),
               min(getDistanceSP(s2,s1.p1),getDistanceSP(s2,s1.p2)));
}

//两个线段的交点(对于直线跟线段也适用，但注意base是在直线上)
Point getCrossPoint(Segment s1,Segment s2){
    Vector base=s2.p2-s2.p1;
    double d1=abs(cross(base,s1.p1-s2.p1));
    double d2=abs(cross(base,s1.p2-s2.p1));
    double t=d1/(d1+d2);
    return s1.p1+(s1.p2-s1.p1)*t;
}

/* 直线正交
 * 判断向量a，b是否正交 =》a，b的内积为0
 */
bool isOrthogonal(Vector a,Vector b){
    return equals(dot(a,b),0.0);
}

bool isOrthogonal(Point a1,Point a2,Point b1,Point b2){
    return isOrthogonal(a1-a2,b1-b2);
}

/* 直线平行
 * 判断向量a，b是否平行 =》a，b的内积为0
 */
bool isParallel(Vector a,Vector b){
    return equals(cross(a,b),0.0);
}

bool isParallel(Point a1,Point a2,Point b1,Point b2){
    return isParallel(a1-a2,b1-b2);
}

// *********圆***********
struct Circle{
    Point c;
    double r;
    Circle(Point c = Point() ,double r = 0.0 ):c(c),r(r){}
    //求与当前点所成的极角为a的点坐标
    Point point(double a){
        return Point(c.x+r*cos(a),c.y+r*sin(a));
    }
};

//两个圆的位置关系
const int SEPARATION = 4;        //相离
const int EXTERNAL_CUT = 3;      //外切
const int INTERSECTION = 2;      //相交
const int INTERNAL_CUT = 1;      //内切
const int INCLUDE = 0;           //内含

int getCircleToCircle(Circle c1,Circle c2){
    double dis=getDistance(c1.c,c2.c);
    if(c1.r+c2.r<dis){
        return SEPARATION;
    }else if(c1.r+c2.r==dis){
        return EXTERNAL_CUT;
    }else {
        if(sign(fabs(c1.r-c2.r)-dis)==0) return INTERNAL_CUT;
        else if(sign(fabs(c1.r-c2.r)-dis)==1) return INCLUDE;
        return INTERSECTION;
    }
}

/* 圆与直线的交点
 * 交点为一个的时候返回两个相同的点
 * 没有交点则退出
 */

bool intersect(Circle c,Line l){
    return sign(getDistanceLP(l,c.c)-c.r)<=0;
}

pair<Point,Point> getCrossPoints(Circle c,Line l){
    assert(intersect(c,l));         //没有交点
    Point pr=project(l,c.c);
    Vector e=(l.p2-l.p1)/(l.p2-l.p1).abs();
    double base=sqrt(c.r*c.r-(pr-c.c).norm());
    return make_pair(pr+e*base,pr-e*base);
}


//圆与圆的交点

bool intersect(Circle c1,Circle c2){
    return sign(getDistance(c1.c,c2.c)-(c1.r+c2.r))<=0;
}

double arg(Vector p){
    return atan2(p.y,p.x);// double atan2(double y,double x) 返回的是原点至点(x,y)的方位角，即与 x 轴的夹角。返回值的单位为弧度，取值范围为(-PI,PI]
}

Vector polar(double r,double a){
    return Point(cos(a)*r,sin(a)*r);
}

pair<Point,Point> getCrossPoints(Circle c1,Circle c2){
    assert(intersect(c1,c2));
    double d=(c1.c-c2.c).abs();
    double a=acos((c1.r*c1.r+d*d-c2.r*c2.r)/(2*c1.r*d));
    double t=arg(c2.c-c1.c);
    return make_pair(c1.c+polar(c1.r,t+a),c1.c+polar(c1.r,t-a));
}

// 园外一点与圆构成的两个切点。
Point rotate(Point base,Point a,double r){      //a-base 向量旋转r度。
  Point b=a-base;
  a.x=b.x*cos(r)-b.y*sin(r);                // + - 注意方向
  a.y=b.x*sin(r)+b.y*cos(r);
  a=a+base;
  return a;
}

pair<Point,Point> getTangent(Circle c,Point p){
  Vector v=p-c.c;
  double r=acos(c.r/v.abs());
  v=v*c.r/v.abs();
  Point p1=rotate(c.c,c.c+v,r);
  Point p2=rotate(c.c,c.c+v,2*PI-r);
  return make_pair(p1,p2);
}

/*   多边形  */
typedef vector<Point> Polygon;

//点的****内包*****(判断点与多边形的关系)
//多边形内返回2
//多边形上返回1
//多边形外返回0
int contains(Polygon g,Point p){
    int n=g.size();
    bool x=false;
    for(int i=0;i<n;i++){
        Point a=g[i]-p,b=g[(i+1)%n]-p;
        if(abs(cross(a,b))<EPS&&dot(a,b)<EPS) return 1;
        if(a.y>b.y) swap(a,b);
        if(a.y<EPS&&EPS<b.y&&cross(a,b)>EPS) x=!x;
    }
    return (x?2:0);
}

/* *******凸包*****(包含点集合p中所有点的最小凸多边形)
 * 输出凸多边形最下端最左侧的顶点为起点,按逆时针方向依次输出坐标。
 * 安德鲁算法 O(n*logn)
 */

double Area(Point p0,Point p1,Point p2){
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}

Polygon andrewscanf(Polygon s){
    int n=s.size();
    sort(s.begin(),s.end());    //x从小到大，x相同的y从小到大
    Polygon u;
    //构建凸包上部
    for(int i=0;i<n;i++){
        for(int j=u.size();j>=2&&Area(u[j-2],u[j-1],s[i]) <= EPS;j--){
            u.pop_back();
        }
        u.push_back(s[i]);
    }
    //构建凸包下部
    int tmp=u.size()+1;
    for(int i=n-2;i>=0;i--){
        for(int j=u.size();j>=tmp&&Area(u[j-2],u[j-1],s[i]) <= EPS;j--){
            u.pop_back();
        }
        u.push_back(s[i]);
    }
    //按顺序生成凸包点的序列
    if(n>1) u.pop_back();               //开始点多加入了一次
    return u;
}

//旋转卡壳*-------》计算凸包直径
double RC(Polygon v){
    double res=0;
    int n=v.size();
    int k=1;
    for(int i=0;i<n;i++){
        while(sign(Area(v[i],v[(i+1)%n],v[(k+1)%n])-Area(v[i],v[(i+1)%n],v[k%n]))==1) k=(k+1)%n;
        res=max(res,max((v[i]-v[k]).abs(),(v[(i+1)%n]-v[k]).abs()));
    }
    return res;
}

//  平面上最近点对。（分治  nlognlogn）
Point a[100005],b[100005];

inline bool CmpY(Point a,Point b){
    return a.y<b.y;
}

double Divide_Conquer(int l,int r){
    if(l==r) return inf;
    if(l+1==r) return getDistance(a[l],a[r]);
    int mid=l+r>>1;
    double ans=min(Divide_Conquer(l,mid),Divide_Conquer(mid+1,r));
    int len=0;
    for(int i=l;i<=r;i++){
        if(fabs(a[mid].x-a[i].x)<=ans) b[len++]=a[i];
    }
    sort(b,b+len,CmpY);
    for(int i=0;i<len;i++){
        for(int j=i+1;j<len&&(b[j].y-b[i].y<ans);j++){
            ans=min(ans,getDistance(b[i],b[j]));
        }
    }
    return ans;
}

inline void solve(int n){
    sort(a,a+n);
    printf("%.10f\n",Divide_Conquer(0,n-1));
}


// 圆的公切线，返回的是共切线的条数。
// a[]与b[]分别是圆A与圆B的切点。
int getTangents(Circle A, Circle B, Point *a, Point *b){
    int cnt = 0;        //存切点用
    if(sign(A.r - B.r) < 0){
        swap(A, B);
        swap(a, b);
    }
    double d = sqrt((A.c.x - B.c.x) * (A.c.x - B.c.x) + (A.c.y - B.c.y) * (A.c.y - B.c.y));     //圆心距
    double rdiff = A.r - B.r;      //两圆半径差
    double rsum = A.r + B.r;       //两圆半径和
    if(sign(d - rdiff) < 0) return 0;        //1.内含
    double base = atan2(B.c.y - A.c.y, B.c.x - A.c.x);      //向量AB的极角
    if(sign(d) == 0) return -1;        //2.重合
    if(sign(d - rdiff) == 0){       //3.内切
        a[cnt] = b[cnt] = A.point(base);
        cnt++;
        return 1;
    }
    double ang = acos((A.r - B.r) / d);
    a[cnt] = A.point(base + ang); b[cnt] = B.point(base + ang); cnt++;      //4.相交（外切、外离的外公切线也在此求出）
    a[cnt] = A.point(base - ang); b[cnt] = B.point(base - ang); cnt++;      //两条外公切线的切点
    if(sign(d - rsum) == 0){        //5.外切
        a[cnt] = b[cnt] = A.point(base);
        cnt++;
    }
    else if(sign(d - rsum) > 0){      //6.外离
        double ang = acos((A.r + B.r) / d);
        a[cnt] = A.point(base + ang); b[cnt] = B.point(PI + base + ang); cnt++;
        a[cnt] = A.point(base - ang); b[cnt] = B.point(PI + base - ang); cnt++;
    }
    return cnt;

}

int main(){
    Circle A,B;
    Point a[5],b[5];
    while(scanf("%lf%lf%lf%lf%lf%lf",&A.c.x,&A.c.y,&A.r,&B.c.x,&B.c.y,&B.r)!=EOF)
        {
        bool flag=0;
        if(sign(A.r - B.r) < 0) flag=1;
        int cnt=getTangents(A,B,a,b);
//        printf("%d\n",cnt);
        if(cnt==-1||cnt==0) continue;
        vector<Point> v;
        for(int i=0;i<cnt;i++){
            v.push_back(a[i]);
        }
        sort(v.begin(),v.end());
        for(int i=0;i<cnt;i++){
            printf("%.10f %.10f\n",v[i].x,v[i].y);
        }
    }
    return 0;
}