!Double Geometry

//
//
//
//            IF INPUT IS DOUBLE, CHANGE IT IN READ METHODS
//            SET PRECISION IN YOUR PROGRAM TO OUTPUT POINTS
//
//

const ld eps = 1e-8;
const ld PI = atan2(0, -1);
const ld INF = 1e15;


ld sqr(ld a)
{
    return a * a;
}

ld my_abs(ld a)
{
    if (a < 0)
        return -a;
    return a;
}

bool eq(ld a, ld b)
{
    return my_abs(a - b) < eps;
}

bool neq(ld a, ld b)
{
    return my_abs(a - b) > eps;
}

bool leq(ld a, ld b)
{
    return a < b || eq(a, b);
}

bool le(ld a, ld b)
{
    return a < b && !eq(a, b);
}


bool geq(ld a, ld b)
{
    return a > b || eq(a, b);
}


bool ge(ld a, ld b)
{
    return a > b && !eq(a, b);
}

ld my_sqrt(ld a)
{
    if(le(a, (ld)0))
    {
#ifdef ONPC
        assert("my_sqrt OF NEGATIVE NUMBER");
#endif
        return 0;
    }
    if(a < 0)
        return 0;
    return sqrtl(a);
}

/*----------------------------------------Point------------------------------*/

struct Point
{
    ld x, y;

    Point():
        x(0),
        y(0) {}
    Point(ld x, ld y):
        x(x),
        y(y) {}

    Point operator-() const
    {
        return Point(-x, -y);
    }

    Point operator+(const Point &a) const
    {
        return Point(a.x + x, a.y + y);
    }

    void operator+=(const Point &a)
    {
        x += a.x;
        y += a.y;
    }

    Point operator-(const Point &a) const
    {
        return Point(x - a.x, y - a.y);
    }

    void operator-=(const Point &a)
    {
        x -= a.x;
        y -= a.y;
    }

    ld operator^(const Point &a) const
    {
        return x * a.y - y * a.x;
    }

    ld operator*(const Point &a) const
    {
        return x * a.x + y * a.y;
    }

    Point operator*(const ld &a) const
    {
        return Point(x * a, y * a);
    }

    friend Point operator*(const ld &a, const Point &p);

    void operator*=(const ld &a)
    {
        x *= a;
        y *= a;
    }

    Point operator/(const ld &a) const
    {
        return Point(x / a, y / a);
    }

    void operator/=(const ld &a)
    {
        x /= a;
        y /= a;
    }

    ld len() const
    {
        return my_sqrt(x * x + y * y);
    }

    ld dist(const Point &a) const
    {
        return (*this - a).len();
    }

    bool operator<(const Point &a) const
    {
        return le(y, a.y) || (eq(y, a.y) && le(x, a.x));
    }

    bool operator>(const Point &a) const
    {
        return ge(y, a.y) || (eq(y, a.y) && ge(x, a.x));
    }

    bool operator==(const Point &a) const
    {
        return eq(a.x, x) && eq(a.y, y);
    }

    bool operator!=(const Point &a) const
    {
        return neq(a.x, x) || neq(a.y, y);
    }

    void read()
    {
        ll a, b;
        cin >> a >> b;
        x = a;
        y = b;
    }

    void write() const
    {
        cout << x << ' ' << y << '\n';
    }

    void debwrite() const
    {
        cerr << fixed << setprecision(2) << "Point: x: " << x << ", y: " << y << endl;
    }

    Point get_norm(const ld &k = 1) const
    {
        ld len = my_sqrt(x * x + y * y);
        if (eq(len, 0))
        {
#ifdef ONPC
            assert("NORMALIZING ZERO VECTOR");
#endif
            return *this;
        }
        return Point(x / len * k, y / len * k);
    }

    void normalize(const ld &k = 1)
    {
        Point p = Point(x, y).get_norm(k);
        x = p.x;
        y = p.y;
    }

    Point rotate() const
    {
        return Point(-y, x);
    }

    Point rotate(const ld &cosa, const ld &sina) const
    {
        Point v = Point(x, y);
        Point u = v.rotate();
        return v * cosa + u * sina;
    }

    Point rotate(const ld &al) const
    {
        return rotate(cos(al), sin(al));
    }

    bool is_zero() const
    {
        return eq(x, 0) && eq(y, 0);
    }

    ld angle() const
    {
        return atan2(y, x);
    }
};

Point operator*(const ld &a, const Point &p)
{
    return Point(a * p.x, a * p.y);
}

/*-----------------------------------------Line------------------------------*/


struct Line
{
    ld a, b, c;

    Line():
        a(1),
        b(1),
        c(0) {}

    Line(ld a, ld b, ld c):
        a(a),
        b(b),
        c(c) {}

    Line(Point a, Point b):
        a(a.y - b.y),
        b(b.x - a.x),
        c((b.y - a.y) * a.x + (a.x - b.x) * a.y) {}

    ld len() const
    {
        return my_sqrt(a * a + b * b);
    }

    ld operator()(const Point &p) const
    {
        return a * p.x + b * p.y + c;
    }

    void normalize()
    {
        ld z = my_sqrt(a * a + b * b);
        if (neq(z, 0))
        {
            a /= z;
            b /= z;
            c /= z;
        }
        else
        {
#ifdef ONPC
            assert("normalizing (0, 0, 0) line");
#endif
        }
    }

    Point cross(const Line &l) const
    {
        return Point(-(b * l.c - l.b * c) / (b * l.a - l.b * a), -(a * l.c - l.a * c) / (a * l.b - l.a * b));
    }

    Point intersect(const Line &l) const
    {
        return Point(-(b * l.c - l.b * c) / (b * l.a - l.b * a), -(a * l.c - l.a * c) / (a * l.b - l.a * b));
    }

    bool parallel(const Line &l) const
    {
        return eq(0, l.a * b - l.b * a);
    }

    ld dist(const Point &p) const
    {
        return my_abs(p.x * a + p.y * b + c) / my_sqrt(a * a + b * b);
    }

    int dir(const Point &p) const
    {
        ld t = p.x * a + p.y * b + c ;
        if (eq(t, 0))
            return 0;
        if (ge(t, 0))
            return 1;
        return -1;
    }

    bool lies(const Point &p) const
    {
        return my_abs(a * p.x + b * p.y + c) < eps;
    }

    Line perpendicular() const
    {
        return Line(-b, a, 0);
    }

    Line perpendicular(const Point &p) const
    {
        return Line(-b, a, p.x * b - p.y * a);
    }

    void read()
    {
        ll x, y, z;
        cin >> x >> y >> z;
        a = x;
        b = y;
        c = z;
    }

    void write()
    {
        cout << a << ' ' << b << ' ' << c << '\n';
    }

    void debwrite()
    {
#ifdef ONPC
        cerr << fixed << setprecision(2) << "Line: a = " << a << ", b = " << b << ", c = " << c << endl;
#endif
    }
};


/*-----------------------------------------Circle------------------------------------------*/


struct Circle
{
    Point c;
    ld r;

    Circle():
        c(Point(0, 0)),
        r(1) {}

    Circle(Point c, ld r):
        c(c),
        r(r) {}

    Circle(ld x, ld y, ld r):
        c(Point(x, y)),
        r(r) {}

    Circle(Point c, Point a):
        c(c),
        r((c - a).len()) {}

    ld len() const
    {
        return (ld)2 * PI * r;
    }

    ld square() const
    {
        return PI * r * r;
    }

    void read()
    {
        ll a, b, d;
        cin >> a >> b >> d;
        c.x = a;
        c.y = b;
        r = d;
    }

    void write() const
    {
        cout << c.x << ' ' << c.y << ' ' << r << '\n';
    }

    void debwrite() const
    {
#ifdef ONPC
        cerr << fixed << setprecision(2) << "Circle: ceneter = (" << c.x << ", " << c.y << "); radius = " << r << endl;
#endif
    }
};

ld dist(const Point &a, const Point &b)
{
    return (a - b).len();
}

Point lines_cross(Line l, Line k)
{
    l.normalize();
    k.normalize();
    return l.cross(k);
}

Point lines_intersect(Line l, Line k)
{
    l.normalize();
    k.normalize();
    return l.cross(k);
}


bool parallel(Line l, Line k)
{
    l.normalize();
    k.normalize();
    return l.parallel(k);
}

bool point_on_line(Point p, Line l)
{
    l.normalize();
    return l.lies(p);
}

bool point_on_line(Line l, Point p)
{
    l.normalize();
    return l.lies(p);
}

bool three_points_on_line(Point a, Point b, Point c)
{
    a -= b;
    b -= c;
    return my_abs(a ^ b) / a.len() / b.len() < eps;
}

bool collinear(Point a, Point b, const Point &c)
{
    a -= c;
    b -= c;
    return my_abs(a ^ b) / a.len() / b.len() < eps;
}

Line perp(const Point &p, Line l)
{
    l.normalize();
    return l.perpendicular(p);
}

Line perp(Line l, Point p)
{
    l.normalize();
    return l.perpendicular(p);
}

ld dist_to_line(const Point &p, Line l)
{
    l.normalize();
    return l.dist(p);
}

ld dist_to_line(Line l, const Point &p)
{
    l.normalize();
    return l.dist(p);
}

ld dist_to_ray(const Point &p, const Point &a, const Point &b)
{
    if ((b - a) * (p - a) / (b - a).len() / (p - a).len() > eps)
        return dist_to_line(p, Line(a, b));
    return p.dist(a);
}

bool point_on_ray(const Point &p, const Point &a, const Point &b)
{
    return eq(0, dist_to_ray(p, a, b));
}

ld dist_to_segment(const Point &p, const Point &a, const Point &b)
{
    return max(dist_to_ray(p, a, b), dist_to_ray(p, b, a));
}

bool point_on_segment(const Point &p, const Point &a, const Point &b)
{
    return eq(0, dist_to_segment(p, a, b));
}

ld angle(Point A, const Point &O, Point B)
{
    A -= O;
    B -= O;
    return acos((A * B) / A.len() / B.len());
}

ld angle(const Point &A, const Point &B)
{
    return acos((A * B) / A.len() / B.len());
}

bool point_in_angle(Point P, Point A, const Point &O, Point B)
{
    P -= O;
    A -= O;
    B -= O;
    if (le((B ^ A) / A.len() / B.len(), 0))
        swap(A, B);
    return geq((A ^ P) / A.len() / P.len(), 0) && geq((P ^ B) / P.len() / B.len(), 0);
}

vector<Point> segments_cross(Point A, Point B, Point C, Point D)
{
    if (three_points_on_line(A, B, C) && three_points_on_line(A, B, D))
    {
        if (A > B)
            swap(A, B);
        if (C > D)
            swap(C, D);
        if (C > B)
            return {};
        if (C == B)
            return {C};
        return {B, C};
    }
    Line l1 = Line(A, B), l2 = Line(C, D);
    if (parallel(l1, l2))
        return {};
    Point X = lines_cross(l1, l2);
    if (point_on_segment(X, A, B) && point_on_segment(X, C, D))
        return {X};
    return {};
}

bool check_rays_cross(const Point &A, const Point &B, const Point &C, const Point &D)
{
    Line l1 = Line(A, B), l2 = Line(C, D);
    if (parallel(l1, l2))
        return 0;
    Point X = lines_cross(l1, l2);
    return point_on_ray(X, A, B) && point_on_ray(X, C, D);
}

Point in_center(const Point &A, const Point &B, const Point &C)
{
    ld a = (C - B).len();
    ld b = (A - C).len();
    ld c = (A - B).len();
    ld s = a + b + c;
    return Point((a * A.x + b * B.x + c * C.x) / s, (a * A.y + b * B.y + c * C.y) / s);
}

Line bissectrice(const Point &A, const Point &B, const Point &C)
{
    return Line(A, in_center(A, B, C));
}

Circle in_circle(const Point &A, const Point &B, const Point &C)
{
    Point I = in_center(A, B, C);
    return Circle(I, dist_to_line(I, Line(A, B)));
}


Point middle(const Point &A, const Point &B)
{
    return (A + B) / (ld)2;
}

Line median(const Point &A, const Point &B, const Point &C)
{
    Point M = middle(A, C);
    return Line(B, M);
}

Point medians_center(const Point &A, const Point &B, const Point &C)
{
    return (A + B + C) / (ld)3;
}

Point masses_center(const vector<Point> &p)
{
    Point ans = p[0];
    for (int i = 1; i < p.size(); i++)
        ans += p[i];
    return ans / (ld)p.size();
}

Point heights_center(const Point &A, const Point &B, const Point &C)
{
    Line AB = Line(A, B), BC = Line(B, C);
    Line l = perp(A, BC), k = perp(C, AB);
    return lines_cross(l, k);
}

Point circum_center(const Point &A, const Point &B, const Point &C)
{
    Point Ma = middle(B, C), Mb = middle(A, C);
    Line BC = Line(B, C), AC = Line(A, C);
    Line l = perp(Ma, BC), k = perp(Mb, AC);
    return lines_cross(l, k);
}

Circle circum_circle(const Point &A, const Point &B, const Point &C)
{
    Point P = circum_center(A, B, C);
    return Circle(P, (P - A).len());
}

ld square(const vector<Point> &p)
{
    ld s = 0;
    int n = p.size();
    for (int i = 0; i < n; i++)
    {
        int j = (i + 1) % n;
        s += (p[i].x - p[j].x) * (p[i].y + p[j].y);
    }
    return s / (ld)2;
}

bool point_on_circle(const Point &P, const Circle &w)
{
    return eq(dist(P, w.c), w.r);
}

bool point_in_circle(const Point &P, const Circle &w)
{
    return leq(dist(P, w.c), w.r);
}

ld dist_to_circle(Point p, Circle w)
{
    return my_abs(w.r - (w.c - p).len());
}

bool point_in_convex_polygon(const Point &A, const vector<Point> &p)
{
    int n = p.size();
    for (int i = 0; i < n; i++)
    {
        int j = (i + 1) % n, k = (i + 2) % n;
        Line l = Line(p[i], p[j]);
        l.normalize();
        if (l(A) * l(p[k]) < -eps)
            return 0;
    }
    return 1;
}

ld arc_length(const Circle &c, const Point &A, const Point &B)
{
    ld alpha = angle(A, c.c, B);
    return alpha * c.r;
}

vector<Point> line_circle_cross(Line l, const Circle &w)
{
    l.normalize();
    vector<Point> v;
    ld d = dist_to_line(w.c, l);
    if (ge(d, w.r))
        return v;
    Point h = w.c - Point(l.a, l.b) * d;
    Point h1 = w.c + Point(l.a, l.b) * d;
    if (my_abs(dist_to_line(h1, l)) < my_abs(dist_to_line(h, l)))
        h = h1;
    if (eq(d, w.r))
    {
        v.push_back(h);
        return v;
    }
    Point vect = Point(-l.b, l.a);
    ld go = my_sqrt(w.r * w.r - d * d);
    Point q = vect * go;
    v.push_back(h + q);
    v.push_back(h - q);
    return v;
}

vector<Point> circles_cross(const Circle &w, const Circle &u)
{
    Point v = (u.c - w.c);
    ld d = v.len();
    v = v / d;
    ld a = (w.r * w.r - u.r * u.r + d * d) / ((ld)2 * d);
    v = w.c + v * a;
    Line l(w.c, u.c);
    Line k = perp(l, v);
    return line_circle_cross(k, w);
}


vector<Line> tangent(const Point &P, const Circle &c)
{
    vector<Line> t;
    if (point_on_circle(P, c))
    {
        Line l = Line(P, c.c);
        Line k = perp(P, l);
        t.push_back(k);
        return t;
    }
    if (point_in_circle(P, c))
        return t;
    Circle w(P, my_sqrt((c.c - P).len() * (c.c - P).len() - c.r * c.r));
    vector<Point> a = circles_cross(w, c);
    return {tangent(a[0], c)[0], tangent(a[1], c)[0]};
}

bool where(Point v)
{
    if (v.y != 0)
        return v.y > 0;
    return v.x > 0;
}

bool convex_hull_cmp(Point v, Point u)
{
    bool x = where(v), y = where(u);
    if (x != y)
        return x;
    ld t = (v ^ u) / v.len() / u.len();
    if (my_abs(t) > eps)
        return t > eps;
    return v.len() < u.len();
}

vector<Point> graham_convex_hull(vector<Point> a)
{
    int n = a.size();
    Point down = a[0];
    for (int i = 1; i < n; i++)
        if (a[i] < down)
            down = a[i];
    for (int i = 0; i < n; i++)
        a[i] -= down;
    sort(a.begin(), a.end(), convex_hull_cmp);
    vector<Point> v;
    for (int i = 0; i < n; i++)
    {
        while (v.size() > 1 && geq(((a[i] - v.back()) ^ (v.back() - v[v.size() - 2])), 0))
            v.pop_back();
        v.push_back(a[i]);
    }
    for (int i = 0; i < v.size(); i++)
        v[i] += down;
    return v;
}

vector<Point> jarvis_convex_hull(vector<Point> a)
{
    int n = a.size();
    if (n < 3)
    {
        if (n == 1)
            return a;
        if (n == 2)
        {
            if (a[0] == a[1])
                return {a[0]};
            return a;
        }
    }
    Point down = a[0];
    int k = 0;
    for (int i = 0; i < n; i++)
        if (a[i] < down)
            k = i, down = a[i];
    vector<Point> v;
    v.push_back(down);
    int cur = k;
    while (true)
    {
        int next = -1;
        for (int i = 0; i < n; i++)
            if (i != cur && (next == -1 || ge(((a[i] - a[cur]) ^ (a[next] - a[cur])), 0) ||
            (eq(((a[i] - a[cur]) ^ (a[next] - a[cur])), 0) && (a[i] - a[cur]).len() > (a[next] - a[cur]).len())))
                next = i;
        if (next == k)
            break;
        v.push_back(a[next]);
        cur = next;
    }
    return v;
}



vector<Point> sum(const vector<Point> &a, const vector<Point> &b)
{
    vector<Point> v, vect;
    v.clear();
    vect.clear();
    int n = a.size();
    int m = b.size();
    Point besta(5e18, 5e18);
    for (int i = 0; i < n; i++)
        if (a[i] < besta)
            besta = a[i];
    Point bestb(5e18, 5e18);
    for (int i = 0; i < m; i++)
        if (b[i] < bestb)
            bestb = b[i];
    Point start = besta + bestb;
    for (int i = 0; i < n; i++)
        vect.push_back(a[(i + 1) % n] - a[i]);
    for (int i = 0; i < m; i++)
        vect.push_back(b[(i + 1) % m] - b[i]);
    sort(vect.begin(), vect.end(), convex_hull_cmp);
    for (int i = 0; i < vect.size(); i++)
    {
        start += vect[i];
        v.push_back(start);
    }
    return v;
}

bool planes_intersect(vector<Line> q)
{
    int n = q.size();
    random_shuffle(q.begin(), q.end());
    Point p;
    if (eq(q[0].a, 0))
    {
        p.x = 0;
        p.y = -q[0].c / q[0].b;
    }
    else
    {
        p.y = 0;
        p.x = -q[0].c / q[0].a;
    }
    for (int i = 1; i < q.size(); i++)
    {
        if (geq(q[i](p), 0))
            continue;
        if (eq(q[i].b, 0))
        {
            ld l = -INF, r = INF;
            for (int j = 0; j < i; j++)
            {
                if (parallel(q[j], q[i]))
                {
                    if (le(q[j](Point(-q[i].c / q[i].a, 0)), 0))
                        return 0;
                    continue;
                }
                Point p = lines_cross(q[i], q[j]);
                Point qq = Point(p.x, p.y + (ld)100);
                if (q[j](qq) > (ld)0)
                    l = max(l, p.y);
                else
                    r = min(r, p.y);
            }
            if (ge(l, r))
                return 0;
            p.x = -q[i].c / q[i].a;
            p.y = l;
        }
        else
        {
            ld l = -INF, r = INF;
            for (int j = 0; j < i; j++)
            {
                if (parallel(q[j], q[i]))
                {
                    if (le(q[j](Point(0, -q[i].c / q[i].b)), 0))
                        return 0;
                    continue;
                }
                Point p = lines_cross(q[i], q[j]);
                Point qq = Point(p.x + (ld)100, -(q[i].c + (p.x + (ld)100) * q[i].a) / q[i].b);
                if (q[j](qq) > (ld)0)
                    l = max(l, p.x);
                else
                    r = min(r, p.x);
            }
            if (ge(l, r))
                return 0;
            p.x = l;
            p.y = -(q[i].c + q[i].a * l) / q[i].b;
        }
    }
    return 1;
}