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 <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <functional>

using namespace std;

#define fst first
#define snd second
#define all(c) ((c).begin()), ((c).end())
#define TEST(x,a) { auto y=(x); if (sign(y-a)) { cout << "line " << __LINE__  << #x << " = " << y << " != " << a << endl; exit(-1); } }


// implementation note: use EPS only this function
// usage note: check sign(x) < 0, sign(x) > 0, or sign(x) == 0
const double EPS = 1e-8;
int sign(double x) {
  const double EPS = 1e-8;
  if (x < -EPS) return -1;
  if (x > +EPS) return +1;
  return 0;
}
struct point {
  typedef double T;
  T x, y; 
  point &operator+=(point p) { x += p.x; y += p.y; return *this; }
  point &operator-=(point p) { x -= p.x; y -= p.y; return *this; }
  point &operator*=(T a)     { x *= a;   y *= a;   return *this; }
  point &operator/=(T a)     { return *this *= (1.0/a); }
  point operator-() const    { return {-x, -y}; }
  bool operator==(point p) const { return !sign(x-p.x) && !sign(y-p.y); }
  bool operator<(point p) const { return x!=p.x ? x<p.x : y<p.y; } // for sort
};
point operator+(point p, point q) { return p += q; }
point operator-(point p, point q) { return p -= q; }
point operator*(point::T a, point p) { return p *= a; }
point operator*(point p, point::T a) { return p *= a; }
point operator/(point p, point::T a) { return p /= a; }
point::T dot(point p, point q) { return p.x*q.x+p.y*q.y; }
point::T cross(point p, point q) { return p.x*q.y-p.y*q.x; } // left turn > 0
point orth(point p) { return {-p.y, p.x}; }

istream &operator>>(istream &is, point &p) { is>>p.x>>p.y;return is; }
ostream &operator<<(ostream &os, point &p) { os<<"("<<p.x<<","<<p.y<<")"; return os; }

struct line { point p, q; };
bool operator==(line l, line m) {
  return !sign(cross(l.p-l.q,m.p-m.q)) && !sign(cross(l.p-l.q,m.p-l.p));
}
struct segment { point p, q; };
bool operator==(segment l, line m) {
  // do not consider the direction
  return (l.p==m.p && l.q==m.q) || (l.p==m.q && l.q==m.p);
}
struct circle { point p; point::T r; };
bool operator==(circle c, circle d) { return c.p == d.p && !sign(c.r - d.r); }

//
// p is on the line l
//
vector<point> intersect(line l, point p) {
  if (sign(cross(l.p, l.q-p)) != 0) return {};
  return {p};
}
vector<point> intersect(point p, line l) {
  return intersect(l, p);
}

vector<point> intersect(segment s, point p) {
  if (sign(cross(s.p-p, s.q-p)) != 0) return {}; 
  if (sign(  dot(s.p-p, s.q-p))  > 0) return {}; // >  for strict intersect
  return {p};                                    // >= for weak intersect
}
vector<point> intersect(point p, segment s) { 
  return intersect(s, p);
}

//
// Crosspoint equation is
//   l.p + (l.q - l.p) t == m.p + (m.q - m.p) s ... (CP.1)
// Taking a cross product with (m.q - m.p), we have
//   (m.q - m.p) x (l.q - l.p) t == (m.q - m.p) x (m.p - l.p) 
//   ~~~~~~~~~~~~a~~~~~~~~~~~~      ~~~~~~~~~~~~b~~~~~~~~~~~~
//
// If a != 0, these two lines have a proper crosspoint.
// If a == 0 and b == 0, these two lines are the same line
// thus any t gives a solution.
// Otherwise, these two lines are parallel.
//
vector<point> intersect(line l, line m) {
  auto a = cross(m.q - m.p, l.q - l.p);
  auto b = cross(l.p - m.p, l.q - l.p); 
  if (sign(a) != 0) return {m.p + b/a*(m.q - m.p)}; // properly crossing
  if (sign(b) == 0) return {m.p, m.q};              // same line
  return {};                                        // disjoint parallel
}

//
// In CP.1, t must be in [0, 1]. Thus 0 <= b/a <= 1 is required.
// By assuming a > 0, it is equivalent to b >= 0 and b-a <= 0
//
vector<point> intersect(line l, segment s) {
  auto a = cross(s.q - s.p, l.q - l.p);
  auto b = cross(l.p - s.p, l.q - l.p); 
  if (a < 0) { a *= -1; b *= -1; }
  if (sign(b) < 0 || sign(a-b) < 0) return {};      // no intersect
  if (sign(a) != 0) return {s.p + b/a*(s.q - s.p)}; // properly crossing
  if (sign(b) == 0) return {s.p, s.q};              // same line
  return {};                                        // disjoint parallel
}

// intersection of two segments
vector<point> intersect(segment s, segment t) {
  auto a = cross(s.q - s.p, t.q - t.p);
  auto b = cross(t.p - s.p, t.q - t.p); 
  auto c = cross(s.q - s.p, s.p - t.p);
  if (a < 0) { a = -a; b = -b; c = -c; }
  if (sign(b) < 0 || sign(a-b) < 0 ||
      sign(c) < 0 || sign(a-c) < 0) return {};      // disjoint
  if (sign(a) != 0) return {s.p + b/a*(s.q - s.p)}; // properly crossing
  vector<point> ps;                                 // same line
  auto insert_if_possible = [&](point p) {
    for (auto q: ps) if (sign(dot(p-q, p-q)) == 0) return;
    ps.push_back(p);
  };
  if (sign(dot(s.p-t.p, s.q-t.p)) <= 0) insert_if_possible(t.p);
  if (sign(dot(s.p-t.q, s.q-t.q)) <= 0) insert_if_possible(t.q);
  if (sign(dot(t.p-s.p, t.q-s.p)) <= 0) insert_if_possible(s.p);
  if (sign(dot(t.p-s.q, t.q-s.q)) <= 0) insert_if_possible(s.q);
  return ps;
}

// reflected point with l
point reflection(point p, line l) {
  auto a = dot(l.p-l.q, l.p-l.q);
  auto b = dot(l.p-p,   l.p-l.q);
  return 2 * (l.p + a/b*(l.q - l.p)) - p;
}

// closest point on l
point projection(point p, line l) {
  auto a = dot(l.p-l.q, l.p-l.q);
  auto b = dot(l.p-p,   l.p-l.q);
  return l.p + a/b*(l.q - l.p);
}

// closest point on s
point projection(point p, segment s) {
  auto a = dot(s.p-s.q, s.p-s.q);
  auto b = dot(s.p - p, s.p-s.q);
  if (sign(b)   < 0) return s.p;
  if (sign(a-b) < 0) return s.q;
  return s.p + b/a*(s.q - s.p);
}

// closest point on c
point projection(point p, circle c) {
  point v = p - c.p;
  return c.p + c.r * v / sqrt(dot(v, v));
}

point::T dist(point p, point q) {
  return sqrt(dot(p - q, p - q));
}
point::T dist(point p, line l) {
  return dist(p, projection(p, l));
}
point::T dist(line l, point p) {
  return dist(p, l);
}
point::T dist(line l, line m) {
  if (sign(cross(l.p-l.q,m.p-m.q))) return 0; // cross
  return dist(l.p, m);
}
point::T dist(point p, segment s) {
  return dist(p, projection(p, s));
}
point::T dist(line l, segment s) {
  if (intersect(l, s).size()) return 0;
  return min(dist(l, s.p), dist(l, s.q));
}
point::T dist(segment s, line l) {
  return dist(l, s); 
}
point::T dist(segment s, segment T) {
  if (intersect(s, T).size()) return 0;
  return min({dist(s.p,T), dist(s.q,T), dist(T.p,s), dist(T.q,s)});
}

//
// intersection points of two circles
//
vector<point> intersect(circle c, circle d) {
  if (c.r < d.r) swap(c, d); 
  auto pow2 = [](point::T a) { return a*a; };
  auto g = dot(c.p-d.p, c.p-d.p);
  if (sign(g) == 0) {
    if (sign(c.r-d.r) != 0) return {};
    return {{c.p.x+c.r, c.p.y}, {c.p.x, c.p.y+c.r}, {c.p.x-c.r, c.p.y}};
  }
  int inner = sign(g-pow2(c.r-d.r));
  int outer = sign(g-pow2(c.r+d.r));
  if (inner < 0 || outer > 0) return {};
  if (inner == 0) return {(c.r*d.p-d.r*c.p)/(c.r-d.r)};
  if (outer == 0) return {(c.r*d.p+d.r*c.p)/(c.r+d.r)};
  auto eta = (pow2(c.r) - pow2(d.r) + g)/(2*g);
  auto mu = sqrt(pow2(c.r)/g - pow2(eta));
  point q = c.p + eta*(d.p-c.p), v = mu*orth(d.p - c.p);
  return {q + v, q - v};
}

// intersection of line and circle
vector<point> intersect(line l, circle c) {
  point u = l.q - l.p, v = l.p - c.p;
  auto a = dot(u,u), b = dot(u,v)/a, t = (dot(v,v) - c.r*c.r)/a;
  auto det = b*b - t;
  if (sign(det) <  0) return {};          // no solution
  if (sign(det) == 0) return {l.p - b*u}; // touch inner/outer
  return {l.p - (b + sqrt(det))*u,        // properly intersect
          l.p - (b - sqrt(det))*u};
}
vector<point> intersect(circle c, line l) {
  return intersect(l, c);
}
bool contains(circle c, point p) {
  return sign(dot(c.p-p, c.p-p) - c.r * c.r) <= 0;
}

//
// 0: not contained in
// 1: on the boundary
// 2: properly contained
//
int contains(vector<point> ps, point p) {
  bool in = false;
  for (int i = 0; i < ps.size(); ++i) {
    point a = ps[i] - p, b = ps[i+1==ps.size()?0:i+1] - p;
    if (a.y > b.y) swap(a, b);
    if (a.y <= 0 && 0 < b.y)
      if (cross(a, b) < 0) in = !in;
    if (sign(cross(a, b)) == 0 && sign(dot(a, b)) <= 0) 
      return 1; // point on the edge
  }
  return in ? 2 : 0; // point in:out the polygon
}

int ccw(point a, point b, point c) {
  b = b - a; c = c - a;
  if(cross(b, c) > 0)     return +1; // counter clockwise
  if(cross(b, c) < 0)     return -1; // clockwise
  if(dot(b, c) < 0)       return +2; // c--a--b on line
  if(dot(b,b) < dot(c,c)) return -2; // a--b--c on line
  return 0;
}
//
// is a convex hull with the smallest number of points.
//
vector<point> convex_hull(vector<point> ps) {
  int n = ps.size(), k = 0;
  sort(all(ps));
  vector<point> ch(2*n);
  auto cond = [&](point p, point q, point o) {
    int a = sign(cross(p-o, q-o)), b = sign(dot(p-o, q-o));
    return a < 0 || (a == 0 && b >= 0); // contains points on the edges
    // return sign(a) < 0; // does not contain points on the edges
  };
  for (int i = 0; i < n; ch[k++] = ps[i++]) // lower-hull
    while (k > 2 && cond(ch[k-2], ch[k-1], ps[i])) ++k;
  for (int i = n-2, t = k; i >= 0; ch[k++] = ps[i--]) // upper-hull
    while (k > t && cond(ch[k-2], ch[k-1], ps[i])) ++k;
  ch.resize(k-1);
  return ch;
}

point::T area(vector<point> ps) {
  if (ps.size() <= 2) return 0;
  auto a = cross(ps.back(), ps[0]);
  for (int i = 0; i+1 < ps.size(); ++i) 
    a += cross(ps[i], ps[i+1]);
  return a/2;
}

vector<point> convex_cut(vector<point> ps, line l) {
  vector<point> qs;
  for (int i = 0; i < ps.size(); ++i) {
    int j = (i == ps.size()-1 ? 0 : i+1);
    if (sign(cross(l.p - ps[i], l.q - ps[i])) >= 0) qs.push_back(ps[i]); 
    if (sign(cross(l.p - ps[i], l.q - ps[i])) *
        sign(cross(l.p - ps[j], l.q - ps[j])) < 0) {
      auto a = cross(ps[j] - ps[i], l.q - l.p);
      auto b = cross(l.p - ps[i], l.q - l.p); 
      qs.push_back(ps[i] + b/a*(ps[j] - ps[i]));
    }
  }
  return qs;
}

circle three_point_circle(point p, point q, point r) {
  point u = orth(q - p), v = r - p; 
  point o = (p+q + u*dot(r-q,v)/dot(u,v))/2;
  return {o, sqrt(dot(p - o, p - o))};
}

double quadraliteral_area(double a, double b, double c, double d) {
  double s = a+b+c+d;
  return sqrt((s-a)*(s-b)*(s-c)*(s-d))/4;
}
double triangle_area(double a, double b, double c) {
  return quadraliteral_area(a, b, c, 0);
}
double excircle_radius(double a, double b, double c) {
  return a*b*c/4/triangle_area(a, b, c);
}
double incircle_radius(double a, double b, double c) {
  return 2*triangle_area(a,b,c)/(a+b+c);
}

//
// tangent line to from p to c
//
// Let q be a tangent point.
// The angle between q -- p -- c.p is 
//   sin(t) = r/|p - c.p|.
// and the solution is
//   p + (c.p - p) * exp(\pm it).
//
vector<line> tangent(point p, circle c) {
  point u = p - c.p, v = orth(u);
  auto g = dot(u,u) - c.r*c.r;
  if (sign(g) < 0) return {};
  if (sign(g) == 0) return {{p, p + v}};
  u = u * (c.r*c.r/dot(u,u));
  v = v * (c.r*sqrt(g)/dot(v,v));
  return {{p, c.p + u - v}, {p, c.p + u + v}};
}
vector<line> tangent(circle c, point p) {
  return tangent(p, c);
}

vector<line> tangent(circle c, circle d) {
  if (c.r < d.r) swap(c, d);
  auto g = dot(c.p-d.p, c.p-d.p);
  if (sign(g) == 0) return {}; // same origin
  point u = (d.p-c.p)/sqrt(g), v = orth(u); // coordinate systems
  vector<line> ls;
  for (int s = +1; s >= -1; s -= 2) { 
    auto h = (c.r+s*d.r)/sqrt(g); // = cos(theta)
    if (sign(1 - h*h) == 0) { // touch inner/outer
      ls.push_back({c.p+c.r*u, c.p+c.r*(u+v)});
    } else if (sign(1 - h*h) > 0) { // properly intersect
      point uu = h*u, vv = sqrt(1-h*h)*v;
      ls.push_back({c.p+c.r*(uu+vv), d.p-d.r*(uu+vv)*s});
      ls.push_back({c.p+c.r*(uu-vv), d.p-d.r*(uu-vv)*s});
    }
  }
  return ls;
}


void angular_sort(vector<point> &ps) {
  point o = {0, 0};
  auto comp = [&](point p, point q) {
    p = p - o; q = q - o;
    if (sign(p.y) != sign(q.y)) return p.y > q.y; 
    if (!sign(p.y) && !sign(q.y)) { 
      if (sign(p.x) >= 0 || sign(q.x) >= 0) return p.y > q.y; 
      else                                  return p.x < q.x;
    }
    if (sign(cross(p, q))) return cross(p, q) < 0;
    return dot(p, p) > dot(q, q);
  };
  sort(all(ps));
}


/*
int maximum_points_on_a_line(vector<point> ps) {
  sort(all(ps)); // assume dx >= 0; if dx == 0 then dy >= 0
  int max_count = 0;
  for (int i = 0; i < ps.size(); ) {
    int k = 1;
    while (sign(norm(ps[i] - ps[i+k])) == 0) ++k;

    vector<point> slope;
    for (int j = i+1; j < ps.size(); ++j) 
      slope.push_back(ps[j] - ps[i]);
    auto comp = [&](point p, point q) { return p.y * q.x < q.y * p.x; };
    sort(all(slope), comp);
    for (int i = 0, k; i < slope.size(); i += k) {
      for (k = 1; slope[i] == slope[i+k]; ++k);
      max_count = max(max_count, base + k);
    }
  }
  return max_count;
}
*/


point::T triangulate(vector<point> ps) {
  int n = ps.size();
  vector<int> next(n);
  for (int i = 0; i < n-1; ++i) next[i] = i+1;
  auto is_ear = [&](int i, int j, int k) {
    if (sign(cross(ps[j]-ps[i], ps[k]-ps[i])) <= 0) return false;
    for (int l = next[k]; l != i; l = next[l]) 
      if (sign(cross(ps[i]-ps[l], ps[j]-ps[l])) >= 0
       && sign(cross(ps[j]-ps[l], ps[k]-ps[l])) >= 0
       && sign(cross(ps[k]-ps[l], ps[i]-ps[l])) >= 0) return false;
    return true;
  };
  point::T area = 0;
  for (int i = 0; next[next[i]] != i; ) {
    if (is_ear(i, next[i], next[next[i]])) {
      area  += abs(cross(ps[next[i]]-ps[i], ps[next[next[i]]] - ps[i])) / 2;
      //cout << i << " " << next[i] << " " << next[next[i]] << endl;
      next[i] = next[next[i]];
    } else i = next[i];
  }
  return area;
}


// verify


void verify_intersectCC() {
  auto th = 3.141592653589*rand()/(1.0+RAND_MAX);
  auto dx = 1 - 2*rand()/(1.0+RAND_MAX);
  auto dy = 1 - 2*rand()/(1.0+RAND_MAX);
  auto S = [&](point p) {
    point::T c = cos(th), s = sin(th);
    p.x -= dx; p.y -= dy;
    return (point){c * p.x + s * p.y, -s * p.x + c*p.y};
  };
  auto T = [&](circle C) {
    return (circle){ S(C.p), C.r };
  };
  {
    circle C = { {0,0}, 1 };
    circle D = { {2,0}, 1 };
    TEST(intersect(T(C), T(D)).size(), 1); // touch outer
  }
  {
    circle C = { {0,0}, 1 };
    circle D = { {1,0}, 1 };
    TEST(intersect(T(C), T(D)).size(), 2); // properly intersect inner
  }
  {
    circle C = { {0,0}, 2 };
    circle D = { {1,0}, 1 };
    TEST(intersect(T(C), T(D)).size(), 1); // intersect inner
  }
  {
    circle C = { {0,0}, 2 };
    circle D = { {3,0}, 2 };
    TEST(intersect(T(C), T(D)).size(), 2); // properly intersect outer
  }
  {
    circle C = { {0,0}, 3 };
    circle D = { {1,0}, 1 };
    TEST(intersect(T(C), T(D)).size(), 0); // too close
  }
  {
    circle C = { {0,0}, 1 };
    circle D = { {3,0}, 1 };
    TEST(intersect(T(C), T(D)).size(), 0); // too far
  }
}

double urand() { return rand() / (1.0 + RAND_MAX); }
void verify_three_point_circle() {
  for (int iter = 0; iter < 100; ++iter) {
    point p = {urand(), urand()};
    point q = {urand(), urand()};
    point r = {urand(), urand()};
    circle c = three_point_circle(p, q, r);
    TEST(dot(c.p - p, c.p - p), dot(c.p - q, c.p - q));
    TEST(dot(c.p - p, c.p - p), dot(c.p - r, c.p - r));
  }
}

void verify_triangulate() {
  vector<point> ps;
  ps.push_back({0, 0});
  ps.push_back({2, 0});
  ps.push_back({2, 2});
  ps.push_back({1, 1});
  ps.push_back({0, 2});
  TEST(triangulate(ps), area(ps));
}

void verify_convex_cut() {
  int n;
  scanf("%d", &n);
  vector<point> ps(n);
  for (int i = 0; i < n; ++i) {
    scanf("%lf %lf", &ps[i].x, &ps[i].y);
  }
  int m;
  scanf("%d", &m);
  for (int i = 0; i < m; ++i) {
    line L;
    scanf("%lf %lf %lf %lf", &L.p.x, &L.p.y, &L.q.x, &L.q.y);
    vector<point> qs = convex_cut(ps, L);
    printf("%f\n", area(qs));
  }
}
void verify_convex_cut2() {
  vector<point> ps = {
    {0.,0.},
    {1.,0.},
    {2.,0.},
    {2.,1.},
    {2.,2.},
    {1.,2.},
    {0.,2.},
    {0.,1.}
  };
  line L = {{1,0},{1.5,0}};
  vector<point> qs = convex_cut(ps, L);
  for (auto q: qs) cout << q << " "; cout << endl;
}
void verify_tangent() {
  point p;
  circle c;
  scanf("%lf %lf", &p.x, &p.y);
  scanf("%lf %lf %lf", &c.p.x, &c.p.y, &c.r);
  vector<point> ps;
  for (auto L: tangent(c, p)) {
    if (L.p == p) ps.push_back(L.q);
    else          ps.push_back(L.p);
  }
  sort(all(ps));
  for (auto p: ps)
    printf("%.12f %.12f\n", p.x + EPS, p.y + EPS);
}
void verify_tangentCC() {
  TEST(tangent({{-2.0, 0.0}, 2.0}, {{-2.0, 0.0}, 1.0}).size(), 0);
  TEST(tangent({{-2.0, 0.0}, 2.0}, {{-1.0, 0.0}, 1.0}).size(), 1);
  TEST(tangent({{-2.0, 0.0}, 2.0}, {{-0.5, 0.0}, 1.0}).size(), 2);
  TEST(tangent({{-2.0, 0.0}, 2.0}, {{+1.0, 0.0}, 1.0}).size(), 3);
  TEST(tangent({{-2.0, 0.0}, 2.0}, {{+2.0, 0.0}, 1.0}).size(), 4);
  TEST(tangent({{+2.0, 0.0}, 2.0}, {{+2.0, 0.0}, 1.0}).size(), 0);
  TEST(tangent({{+2.0, 0.0}, 2.0}, {{+1.0, 0.0}, 1.0}).size(), 1);
  TEST(tangent({{+2.0, 0.0}, 2.0}, {{+0.5, 0.0}, 1.0}).size(), 2);
  TEST(tangent({{+2.0, 0.0}, 2.0}, {{-1.0, 0.0}, 1.0}).size(), 3);
  TEST(tangent({{+2.0, 0.0}, 2.0}, {{-2.0, 0.0}, 1.0}).size(), 4);

  for (int iter = 0; iter < 100; ++iter) {
    circle c = {{urand(), urand()}, urand()};
    circle d = {{urand(), urand()}, urand()};
    for (line l: tangent(c, d)) {
      TEST(intersect(l, c).size(), 1);
      TEST(intersect(l, d).size(), 1);
    }
  }
}
void verify_tangentCC2() {
  circle c, d;
  cin >> c.p.x >> c.p.y >> c.r;
  cin >> d.p.x >> d.p.y >> d.r;
  vector<line> ls = tangent(c, d);
  vector<point> ps;
  for (line l: ls) {
    ps.push_back(intersect(l, c)[0]);
  }
  sort(all(ps));
  for (point p: ps) {
    double x = p.x; if (sign(x) == 0) x = 0;
    double y = p.y; if (sign(y) == 0) y = 0;
    printf("%.12f %.12f\n", x, y);
  }
}

int main() {
  //verify_intersectCC();
  //verify_three_point_circle();
  //verify_triangulate();
  //verify_convex_cut2();
  //verify_tangent();
  //verify_tangentCC();
  verify_tangentCC2();
}