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

#define int long long
using db = double;

const db eps = 1e-6;
const db pi = acos(-1);

mt19937 eng(time(0));
uniform_real_distribution<db> rd;

int sgn(db a) {
    if(a > eps) return 1;
    else if(a < -eps) return -1;
    else return 0;
}
// a < b : -1 | a == b : 0 | a > b : 1
int cmp(db a, db b) {
    return sgn(a - b);
}
// x in [a, b]
bool inmid(db x, db a, db b) {
    return sgn(x - a) * sgn(x - b) <= 0;
}

//点
struct point {
    db x, y;
    point operator + (const point &p) const {
        return {x + p.x, y + p.y};
    }
    point operator - (const point &p) const {
        return {x - p.x, y - p.y};
    }
    point operator * (db k) const {
        return {k * x , k * y};
    }
    point operator / (db k) const {
        return {x / k , y / k};
    }
    bool operator == (const point &p) const {
        return cmp(x, p.x) == 0 && cmp(y, p.y) == 0;
    }   
    // 优先比较 x 坐标
    bool operator < (const point &p) const {
        int t = cmp(x, p.x);
        if(t != 0) return t == -1;
        return cmp(y, p.y) == -1;
    }
    // 模长
    db len() {
        return sqrt(x * x + y * y);
    }
    // 模长平方
    db len2() {
        return x * x + y * y;
    }
    // 单位化（模长 > 0）
    point unit() {
        return (*this) / len();
    }
    // 极角 (-pi, pi]
    db getw() {
        return atan2(y, x);
    }
    // 逆时针旋转 k 弧度
    point rot(db k) {
        return {x * cos(k) - y * sin(k), x * sin(k) + y * cos(k)};
    }   
    // 逆时针旋转90°
    point rotleft() {
        return {-y, x};
    }
    // 将向量对称到 (-pi / 2, pi / 2] 半平面上
    point getdel() {
        if(sgn(x) == -1 || (sgn(x) == 0 && sgn(y) == -1)) {
            return (*this) * (-1);
        } else {
            return *this;
        }
    }
    // 判断在 y 轴上侧下侧 ( (-pi, 0] : 0 | (0, pi] : 1 )
    int getP() {
        return sgn(y) == 1 || (sgn(y) == 0 && sgn(x) == -1);
    }
    friend istream &operator >> (istream &is, point &p) {
        return is >> p.x >> p.y;
    }
    friend ostream &operator << (ostream &os, point &p) {
        return os << p.x << " " << p.y;
    }
    
};

// 点与线段关系及交点

// 点 p 在点 a, b 构成的矩形中(包括边界)
bool inmid(point p, point a, point b) {
    return inmid(p.x, a.x, b.x) && inmid(p.y, a.y, b.y);
}
// 点积
db dot(point a, point b) {
    return a.x * b.x + a.y * b.y;
}
// 叉积
db cross(point a, point b) {
    return a.x * b.y - a.y * b.x;
}
// 从点 a 转到点 b 的方向角 (-pi, pi]
db rad(point a, point b) {
    return atan2(cross(a, b), dot(a, b));
}
// a b c (逆时针 : 1 | 顺时针 : -1 | 共线 : 0)
int clockwise(point a, point b, point c) {
    return sgn(cross(b - a, c - a));
}
// 按 (-pi, pi] 极角排序
bool cmpangle(point a, point b) {
    return a.getP() < b.getP() || (a.getP() == b.getP() && sgn(cross(a, b)) > 0);
}
// 点 p 在线段 ab 上
bool onS(point p, point a, point b) {
    return inmid(p, a, b) && sgn(cross(p - a, a - b)) == 0;
}
// 点 p 到直线 ab 的投影点
point proj(point p, point a, point b) {
    point k = b - a;
    return a + k * (dot(p - a, k) / k.len2());
}
// 点 p 关于直线 ab 的对称点
point reflect(point p, point a, point b) {
    return proj(p, a, b) * 2 - p;
}
// 判断直线 ab 和直线 cd 是否相交
bool checkLL(point a, point b, point c, point d) {
    return sgn(cross(b - a, d - c)) != 0;
}
// 求直线 ab 和直线 cd 的交点
point getLL(point a, point b, point c, point d) {
    db w1 = cross(a - c, d - c), w2 = cross(d - c, b - c);
    return (a * w2 + b * w1) / (w1 + w2);
}
// [l1, r1] 和 [l2, r2] 是否有交, 用于判断两线段是否相交
bool intersect(db l1, db r1, db l2, db r2) {
    if(l1 > r1) swap(l1, r1);
    if(l2 > r2) swap(l2, r2);
    return cmp(r1, l2) != -1 && cmp(r2, l1) != -1;
}
// 判断线段 ab 和线段 cd 是否相交（非严格相交）
bool checkSS(point a, point b, point c, point d) {
    return intersect(a.x, b.x, c.x, d.x) && intersect(a.y, b.y, c.y, d.y) && 
    sgn(cross(c - a, d - a) * cross(c - b, c - a)) < 0 &&
    sgn(cross(a - c, b - c) * cross(a - d, b - d)) < 0;
}
// 点 a 与 点 b 的距离
db dis(point a, point b) {
    return (b - a).len(); 
}
// 点 p 到直线 ab 的距离
db disLP(point p, point a, point b) {
    return fabs(cross(b - a, p - a)) / dis(a, b);
}
// 点 p 到线段 ab 的距离
db disSP(point p, point a, point b) {
    point q = proj(p, a, b);
    if(inmid(q, a, b)) return dis(p, q);
    else return min(dis(a, p), dis(b, p));
}
// 线段 ab 到 线段 cd 的距离
db disSS(point a, point b, point c, point d) {
    if(checkSS(a, b, c, d)) return 0;
    else return min({disSP(c, a, b), disSP(d, a, b), disSP(a, c, d), disSP(b, c, d)});
}

// 直线(有向) p[0] -> p[1]
struct line {
    point p[2];
    line() {}
    line(point a, point b) {
        p[0] = a, p[1] = b;
    }
    point& operator [] (int k) {
        return p[k];
    }
    // 点 q 位于直线左侧/半平面上 (严格 : > 0 | 不严格 : >= 0)
    bool include(point q) {
        return sgn(cross(p[1] - p[0], q - p[0])) > 0;
    }
    // 方向向量
    point dir() {
        return p[1] - p[0];
    }
    // 向左平移d, 默认为eps
    line push(db d = eps) {
        point delta = (p[1] - p[0]).rotleft().unit() * d;
        return {p[0] + delta, p[1] + delta};
    }
};
// 直线与直线的交点
point getLL(line l1, line l2) {
    return getLL(l1[0], l1[1], l2[0], l2[1]);
}
// 判断两直线是否平行
bool parallel(line l1, line l2) {
    return sgn(cross(l1.dir(), l2.dir())) == 0;
}
// 判断两直线是否平行且同向
bool sameDir(line l1, line l2) {
    return parallel(l1, l2) && sgn(dot(l1.dir(), l2.dir())) == 1;
}
// 同向则左侧小于右侧，否则按极角排序，用于半平面交
int operator < (line l1, line l2){
    if (sameDir(l1, l2)) return l2.include(l1[0]); 
    return cmpangle(l1.dir(), l2.dir());
}
// l3 半平面上是否包含 l1, l2 的交点, 用于半平面交
int checkpos(line l1, line l2, line l3) {
    return l3.include(getLL(l1, l2));
}
// 半平面交, 逆时针方向 (-pi, pi]
vector<line> getHL(vector<line> L) {
    sort(L.begin(), L.end());
    deque<line> q;
    for(int i = 0; i < (int)L.size(); i++) {
        if(i && sameDir(L[i], L[i-1])) continue;
        while(q.size() > 1 && !checkpos(q[q.size() -  2], q[q.size() - 1], L[i])) q.pop_back();
        while(q.size() > 1 && !checkpos(q[1], q[0], L[i])) q.pop_front();
        q.push_back(L[i]);
    }
    while(q.size() > 2 && !checkpos(q[q.size() -  2], q[q.size() - 1], q[0])) q.pop_back();
    while(q.size() > 2 && !checkpos(q[1], q[0], q[q.size() - 1])) q.pop_front();
    vector<line> ret;
    for(line l : q) {
        ret.push_back(l);
    }
    return ret;
}
// 最近点对 (A 需要先按 x 坐标排序), 答案为closepoint(A, 0, n - 1)
db closepoint(vector<point> &A, int l, int r) {
    if(r - l <= 5) {
        db ans = 1e20;
        for(int i = l; i <= r; i++) {
            for(int j = i + 1; j <= r; j++) {
                ans = min(ans, dis(A[i], A[j]));
            }
        }
        return ans;
    }
    int mid = (l + r) >> 1;
    db ans = min(closepoint(A, l, mid), closepoint(A, mid + 1, r));
    vector<point> B;
    for(int i = l; i <= r; i++) {
        if(abs(A[i].x - A[mid].x) <= ans) {
            B.push_back(A[i]);
        }
    }
    sort(B.begin(), B.end(), [](point a, point b) {
        return a.y < b.y;
    });
    for(int i = 0; i < B.size(); i++) {
        for(int j = i + 1; j < B.size() && B[j].y - B[i].y < ans; j++) {
            ans = min(ans, dis(B[i], B[j]));
        }
    }
    return ans;
}

// 圆 (o, r)
struct circle {
    point o;
    db r;
    // 点 p 是否在圆内 (1 : 圆内 | 0 : 圆上 | -1 : 圆外)
    int inside(point p) {
        return cmp(r, dis(o, p));
    }
};
// 两圆位置关系 (两圆公切线数量)
// 相离 : 4 | 外切 : 3 | 相交 : 2 | 内切 : 1 | 包含 : 0
int checkposCC(circle a, circle b) {
    if(cmp(a.r, b.r) == -1) swap(a, b);
    db d = dis(a.o, b.o);
    int w1 = cmp(d, a.r + b. r), w2 = cmp(d, a.r - b.r);
    if(w1 > 0) return 4;
    else if(w1 == 0) return 3;
    else if(w2 > 0) return 2;
    else if(w2 == 0) return 1;
    else return 0;
}
// 直线与圆的交点, 沿 a->b 的方向给出, 相切有两个
vector<point> getCL(circle c, point a, point b) {
    point k = proj(c.o, a, b);
    db d = c.r * c.r - (k - c.o).len2();
    if(sgn(d) == -1) return {};
    point del = (b - a).unit() * sqrt(max((db)0.0, d));
    return {k - del, k + del};
}
// 两圆交点, 沿圆 c1 逆时针方向给出 (c1, c2不能是同一个圆)
vector<point> getCC(circle c1, circle c2) {
    int pd = checkposCC(c1, c2);
    if(pd == 0 || pd == 4) return {};
    db a = (c2.o - c1.o).len2();
    db cosA = (c1.r * c1.r+ a - c2.r * c2.r) / (2 * c1.r * sqrt(max(a, (db)0.0)));
    db b = c1.r * cosA, c = sqrt(max((db)0.0, c1.r * c1.r - b * b));
    point k = (c2.o - c1.o).unit(), m = c1.o + k * b, del = k.rotleft() * c;
    if(pd == 1 || pd == 3) return {m};
    else return {m - del, m + del};
}
// 点到圆的切点, 沿圆 c 的逆时针方向给出 (未判相对关系)
vector<point> TangentCP(circle k, point p) {
    db a = (p - k.o).len(), b = k.r * k.r / a, c = sqrt(max((db)0.0, k.r * k.r - b * b));
    point t = (p - k.o).unit(), m = k.o + t * b, del = t.rotleft() * c;
    return {m - del, m + del};
}
// 外公切线 k1 切点 -> k2 切点 (k1 和 k2 切点相同时, l[0] 为切点)
// !!! 默认 k1.r > k2.r !!!
vector<line> TangentoutCC(circle k1, circle k2) {
    int pd = checkposCC(k1, k2);
    if(pd == 0) return {};
    else if (pd == 1) {
        point k = getCC(k1, k2)[0];
        return {{k, k + (k1.o - k2.o).rotleft()}};
    }
    if(cmp(k1.r, k2.r) == 0) {
        point del = (k2.o - k1.o).unit().rotleft().getdel();
        return {{k1.o - del * k2.r, k2.o - del * k2.r}, {k1.o + del * k1.r, k2.o + del * k2.r}};
    } else {
        point p = (k2.o * k1.r - k1.o * k2.r) / (k1.r - k2.r);
        vector<point> A = TangentCP(k1, p), B = TangentCP(k2, p);
        vector<line> ans;
        for(int i = 0; i < A.size(); i++) {
            ans.push_back({A[i], B[i]});
        }
        return ans;
    }
}
// 内公切线 k1 切点 -> k2 切点 (k1 和 k2 切点相同时, l[0] 为切点)
// !!! 默认 k1.r > k2.r !!!
vector<line> TangentinCC(circle k1, circle k2) {
    int pd = checkposCC(k1, k2);
    if(pd <= 2) return {};
    if(pd == 3) {
        point k = getCC(k1, k2)[0];
        return {{k, k + (k1.o - k2.o).rotleft()}};
    }
    point p = (k2.o * k1.r + k1.o * k2.r) / (k1.r + k2.r);
    vector<point> A = TangentCP(k1, p), B = TangentCP(k2, p);
    vector<line> ans;
    for(int i = 0; i < A.size(); i++) {
        ans.push_back({A[i], B[i]});
    }
    return ans;
}
// 所有公切线
vector<line> TangentCC(circle k1, circle k2) {
    bool flag = false;
    if(k1.r < k2.r) {
        swap(k1, k2);
        flag = true;
    }
    vector<line> A = TangentoutCC(k1, k2), B = TangentinCC(k1, k2);
    for(line k : B) A.push_back(k);
    if(flag) {
        for(line &k : A) {
            swap(k[0], k[1]);
        }
    }
    return A;
}
// 圆 c 与三角形 c.o a b 的有向面积交
db getarea(circle c, point a, point b) {
    point k = c.o;
    c.o = c.o - k;
    a = a - k, b = b - k;
    int pd1 = c.inside(a), pd2 = c.inside(b);
    vector<point> A = getCL(c, a, b);
    if(pd1 >= 0) {
        if(pd2 >= 0) return cross(a, b) / 2;
        return c.r * c.r * rad(A[1], b) / 2 + cross(a, A[1]) / 2;
    } else if (pd2 >= 0) {
        return c.r * c.r * rad(a, A[0]) / 2 + cross(A[0], b) / 2;
    } else {
        int pd = cmp(c.r, disSP(c.o, a, b));
        if(pd <= 0) {
            return c.r * c.r * rad(a, b) / 2;
        }
        return cross(A[0], A[1]) / 2 + c.r * c.r * (rad(a, A[0]) + rad(A[1], b)) / 2;
    }
} 
// 多边形与圆面积交
db getarea(vector<point> A, circle c) {
    int n = A.size();
    if(n <= 2) return 0;
    A.push_back(A[0]);
    db ans = 0;
    for(int i = 0; i < n; i++) {
        point a = A[i], b = A[i + 1];
        ans += getarea(c, a, b);
    }
    return fabs(ans);
}
// 三角形外接圆
circle getcircle(point a, point b, point c) {
    db a1 = b.x - a.x, b1 = b.y - a.y, c1 = (a1 * a1 + b1 * b1) / 2;
    db a2 = c.x - a.x, b2 = c.y - a.y, c2 = (a2 * a2 + b2 * b2) / 2;
    db d = a1 * b2 - a2 * b1;
    point o = {a.x + (c1 * b2 - c2 * b1) / d, a.y + (a1 * c2 - a2 * c1) /d};
    return {o, dis(o, a)};
}
// 最小圆覆盖
circle getScircle(vector<point> A) {
    shuffle(A.begin(), A.end(), eng);
    circle ans = {A[0], 0};
    for(int i = 1; i < A.size(); i++) {
        if(ans.inside(A[i]) == -1) {
            ans = {A[i], 0};
            for(int j = 0; j < i; j++) {
                if(ans.inside(A[j]) == -1) {
                    ans.o = (A[i] + A[j]) / 2;
                    ans.r = dis(ans.o, A[i]);
                    for(int k = 0; k < j; k++) {
                        if(ans.inside(A[k]) == -1) {
                            ans = getcircle(A[i], A[j], A[k]);
                        }    
                    }
                }
            }
        }
    }
    return ans;
}

// 反演

// 不经过反演中心的圆, 反演后变成另一个不经过反演中心的圆
circle invC2C(point O, double R, circle a) {
    db l1 = (a.o - O).len();
    db rb = (R * R * a.r) / (l1 * l1 - a.r * a.r);
    db l2 = l1 * rb / a.r;
    point b = O + (a.o - O) * (l2 / l1);
    return {b, rb};
}
// 经过反演中心的圆, 反演后变成不经过反演中心的直线
vector<point> invC2L(point O, double R, circle a) {
    db d = R * R / (2 * a.r);
    point k1 = O + (a.o - O).unit() * d;
    point k2 = k1 + (a.o - O).rotleft();
    return {k1, k2};
}
// 不经过反演中心的直线, 反演后变成经过反演中心的圆
circle invL2C(point O, double R, point k1, point k2) {
    db r = R * R / (2 * disLP(O, k1, k2));
    point o = (proj(O, k1, k2) - O).unit() * r + O;
    return {o, r};  
}

// 多边形

// 多边形有向面积
db area(vector<point> A) {
    db ans = 0;
    for(int i = 0; i < A.size(); i++) {
        ans += cross(A[i], A[(i + 1) % A.size()]);
    }
    return ans / 2;
}
// 判断是否是逆时针凸包
bool checkconvex(vector<point> A) {
    int n = A.size();
    if(n <= 2) return false;
    A.push_back(A[0]), A.push_back(A[1]);
    for(int i = 0; i < n; i++) {
        if(sgn(cross(A[i + 1] - A[i], A[i + 2] - A[i])) == -1) return false;
    }
    return true;
}
// 点与简单多边形的位置关系 (2 : 内部 | 1 : 边界 | 0 : 外部)
int contain(vector<point> A, point q) {
    int n = A.size();
    A.push_back(A[0]);
    int pd = 0;
    for(int i = 0; i < n; i++) {
        point u = A[i], v = A[i + 1];
        if(onS(q, u, v)) return 1;
        if(cmp(u.y, v.y) > 0) swap(u, v);
        if(cmp(u.y, q.y) >= 0 || cmp(v.y, q.y) < 0) continue;
        if(sgn(cross(u - v, q - v)) < 0) pd ^= 1;
    }
    return pd << 1;
}
// 求凸包 (flag = 0 : 不严格 | flag = 1 : 严格)
vector<point> ConvexHull(vector<point> A, int flag = 1) {
    int n = A.size();
    if(n == 1) return A;
    if(n == 2) {
        if(A[0] == A[1]) return {A[0]};
        else return A;
    }
    vector<point> ans(2 * n);
    sort(A.begin(), A.end());
    int now = -1;
    for(int i = 0; i < A.size(); i++) {
        while(now > 0 && sgn(cross(ans[now] - ans[now - 1], A[i] - ans[now - 1])) < flag) now--;
        ans[++now] = A[i];
    }
    int pre = now;
    for(int i = n - 2; i >= 0; i--) {
        while(now > pre && sgn(cross(ans[now] - ans[now - 1], A[i] - ans[now - 1])) < flag) now--;
        ans[++now] = A[i];
    }
    ans.resize(now);
    return ans;
}
// 凸包直径
db convexDiameter(vector<point> A) {
    int n = A.size();
    if(n == 2) {
        return dis(A[0], A[1]);
    }
    int now = 0;
    db ans = 0;
    for(int i = 0; i < n; i++) {
        while(true) {
            db s1 = cross(A[(i + 1) % n] - A[i], A[now] - A[i]);
            db s2 = cross(A[(i + 1) % n] - A[i], A[(now + 1) % n] - A[i]);
            if(cmp(s1, s2) <= 0) {
                now = (now + 1) % n;
            } else {
                ans = max({ans, dis(A[now], A[i]), dis(A[now], A[(i + 1) % n])});
                break;
            }
        }
    }
    return ans;
}
// 直线切凸包, 保留直线逆时针的所有点
vector<point> convexcut(vector<point> A, point k1, point k2) {
    int n = A.size();
    A.push_back(A[0]);
    vector<point> ans;
    for(int i = 0; i < n; i++) {
        int w1 = clockwise(k1, k2, A[i]), w2 = clockwise(k1, k2, A[i + 1]);
        if(w1 >= 0) ans.push_back(A[i]);
        if(w1 * w2 < 0) ans.push_back(getLL(k1, k2, A[i], A[i + 1]));
    }
    return ans;
}
// 多边形与直线是否严格相交
bool checkPos(vector<point> A, point k1, point k2) {
    struct ins {
        point m, u, v;
        bool operator < (const ins& k) const {
            return m < k.m;
        }
    };
    vector<ins> B;
    vector<point> poly = A;
    A.push_back(A[0]);
    for(int i = 1; i < A.size(); i++) {
        if(!checkLL(A[i - 1], A[i], k1, k2)) continue;
        point m = getLL(A[i - 1], A[i], k1, k2);
        if(inmid(m, A[i - 1], A[i])) {
            B.push_back({m, A[i - 1], A[i]});
        }
    }
    if(B.size() == 0) return false;
    sort(B.begin(), B.end());
    int now = 1;
    while(now < B.size() && B[now].m == B[now].m) now++;
    if(now == B.size()) return false;
    int flag = contain(poly, (B[0].m + B[now].m) / 2);
    if(flag == 2) return true;
    point d = B[now].m - B[0].m;
    for(int i = now; i < B.size(); i++) {
        if(!(B[i].m == B[i - 1].m) && flag == 2) return true;
        int tag = sgn(cross(B[i].v - B[i].u, B[i].m + d - B[i].u));
        if(B[i].m == B[i].u || B[i].m == B[i].v) flag += tag;
        else flag += tag * 2;
    }
    return flag == 2;
}
// 快速检查线段与多边形是否严格相交
bool checkinp(point r, point l, point m) {
    if(cmpangle(l, r)) return cmpangle(l, m) && cmpangle(m, r);
    return cmpangle(l, m) || cmpangle(m, r);
}
bool checkPosFast(vector<point> A, point k1, point k2) {
    if(contain(A, k1) || contain(A, k2)) return true;
    if(k1 == k2) return false;
    A.push_back(A[0]), A.push_back(A[1]);
    for(int i = 1; i < A.size(); i++) {
        if(!checkLL(A[i - 1], A[i], k1, k2)) continue;
        point now = getLL(A[i - 1], A[i], k1, k2);
        if((!inmid(now, A[i - 1], A[i])) || (!inmid(now, k1, k2))) continue;
        if(now == A[i]) {
            if(A[i] == k2) continue;
            point pre = A[i - 1], ne = A[i + 1];
            if(checkinp(pre - now, ne - now, k2 - now)) return true;
        } else if(now == k1) {
            if(k1 == A[i - 1] || k1 == A[i]) continue;
            if(checkinp(A[i - 1] - k1, A[i] - k1, k2 - k1)) return true;
        } else if(now == k2 || now == A[i - 1]) continue;
        else return true;
    }
    return false;
}
// 经过点 p 切凸包的两个切点, 返回下标 [fi, se]
// !!! 需要保证 p 严格在凸包外侧, 凸包点数 >= 3 !!!
// !!! 保证凸包是严格的, 无三点共线 !!!
pair<int, int> getTangentCop(const vector<point> &A, point p) {
    int n = A.size();
    pair<int, int> ans;
    int flag = 1;
    if(clockwise(A[n - 1], A[0], p) == -1) flag = -1;
    int l = 0, r = n - 1, t = 0;
    while(l < r) {
        int mid = (l + r) >> 1;
        if(clockwise(A[mid], A[mid + 1], p) == flag && clockwise(A[0], A[mid + 1], p) == flag) t = l = mid + 1;
        else r = mid;
    }
    ans.first = t;
    l = t, r = n - 1, t = n - 1;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if(clockwise(A[mid], A[mid + 1], p) == flag) t = r = mid;
        else l = mid + 1;
    }
    ans.second = t;
    if(flag == -1) swap(ans.first, ans.second);
    return ans;
}
// 判断点是否在凸多边形内部 (flag = 1 : 严格 | 0 : 不严格)
// !!! 需保证凸包点数>=3 !!!
bool containCoP(const vector<point> &A, point p, int flag = 1) {
    int n = A.size();
    if(!flag && (onS(p, A[0], A[1]) || onS(p, A[n - 1], A[0]))) return true;
    if(!(clockwise(A[0], A[1], p) == 1 && clockwise(A[n - 1], A[0], p) == 1)) return false;
    int l = 1, r = n - 1, ans = 1;
    while(l < r) {
        int mid = (l + r) >> 1;
        if(clockwise(A[0], A[mid], p) == 1) {
            ans = mid;
            l = mid + 1;
        } else r = mid;
    }
    return clockwise(A[ans], A[ans + 1], p) >= flag;
}
// 将凸包拆分为上下凸壳 (需要提前特判一个点的情况)
void getUDP(vector<point> A, vector<point> &U, vector<point> &D) {
    db rad = rd(eng) * 2 * pi;
    for(point p : A) p.rot(rad);
    db l = 1e100, r = -1e100;
    for(point p : A) {
        l = min(l, p.x);
        r = max(r, p.x);
    }
    int wherel, wherer;
    for(int i = 0; i < A.size(); i++) {
        if(cmp(A[i].x, l) == 0) wherel = i;
    }
    for(int i = A.size(); i; i--) {
        if(cmp(A[i - 1].x, r) == 0) wherer = i - 1;
    }
    U.clear(), D.clear();
    int now = wherel;
    while(true) {
        D.push_back(A[now]);
        if(now == wherer) break;
        now++;
        if(now >= A.size()) now = 0;
    }
    now = wherel;
    while(true) {
        U.push_back(A[now]);
        if(now == wherer) break;
        now--;
        if(now < 0) now = A.size() - 1;
    }
    for(point p : U) p.rot(-rad);
    for(point p : D) p.rot(-rad);
}
// 求沿 d 的方向, 凸包的上方切点和下方切点
pair<point, point> getTangentCow(const vector<point> &U, const vector<point> &D, point d) {
    if(sgn(d.x) < 0 || (sgn(d.x) == 0 && sgn(d.y) < 0)) d = d * (-1);
    if(sgn(d.x) == 0) return {U.front(), U.back()};
    int l = 0, r = U.size() - 1, ans = 0;
    point whereU, whereD;
    while(l < r) {
        int mid = (l + r) >> 1;
        if(sgn(cross(U[mid + 1] - U[mid], d)) <= 0) {
            l = mid + 1;
            ans = mid + 1;
        } else r = mid;
    }
    whereU = U[ans];
    l = 0, r = D.size() - 1, ans = 0;
    while(l < r) {
        int mid = (l + r) >> 1;
        if(sgn(cross(D[mid + 1] - D[mid], d) >= 0)) {
            l = mid + 1;
            ans = mid + 1;
        } else r = mid;
    }
    whereD = D[ans];
    return {whereU, whereD};
}
// 闵可夫斯基和 (A, B是凸包, flag = 1 : 严格 | flag = 0 : 非严格)
vector<point> Minkowski(vector<point> A, vector<point> B, int flag = 1) {
    vector<point> ans;
    int n = A.size(), m = B.size();
    A.push_back(A.front()), B.push_back(B.front());
    ans.push_back(A.front() + B.front());
    int t1 = 1, t2 = 1;
    while(t1 <= n && t2 <= m) {
        point s1 = A[t1] - A[t1 - 1], s2 = B[t2] - B[t2 - 1];
        int pd = sgn(cross(s1, s2));
        if(pd >= flag) {
            ans.push_back(ans.back() + s1);
            t1++;
        } else if(pd < 0) {
            ans.push_back(ans.back() + s2);
            t2++;
        } else {
            ans.push_back(ans.back() + s1 + s2);
            t1++, t2++;
        }
    }
    while(t1 <= n) {
        ans.push_back(ans.back() + A[t1] - A[t1 - 1]);
        t1++;
    }
    while(t2 <= m) {
        ans.push_back(ans.back() + B[t2] - B[t2 - 1]);
        t2++;
    }
    return ans;
}


struct P3 {
    db x, y, z;
    P3 operator + (P3 p) {
        return {x + p.x, y + p.y, z + p.z};
    }
    P3 operator - (P3 p) {
        return {x - p.x, y - p.y, z - p.z};
    }
    P3 operator * (db k) {
        return {x * k, y * k, z * k};
    }
    P3 operator / (db k) {
        return {x / k, y / k, z / k};
    }
    bool operator == (const P3 p) {
        return cmp(x, p.x) == 0 && cmp(y, p.y) == 0 && cmp(z, p.z) == 0;
    }
    bool operator < (const P3 p) const {
        int t1 = cmp(x, p.x), t2 = cmp(y, p.y);
        if(t1 != 0) return t1 == -1;
        if(t2 != 0) return t2 == -1;
        return cmp(z, p.z) == -1;
    }
    db len2() {
        return x * x + y * y + z * z;
    }
    db len() {
        return sqrt(len2());
    }
    P3 unit() {
        return (*this) / len();
    }
    friend istream &operator >> (istream &is, P3 &p) {
        return is >> p.x >> p.y >> p.z;
    }
    friend ostream &operator << (ostream &os, P3 &p) {
        return os << p.x << " " << p.y << " " << p.z;
    }
};
// 叉积
P3 cross(P3 a, P3 b) {
    return {a.y * b.z - a.z * b.y, a.z * b.x - a.x * b.z, a.x * b.y - a.y * b.x};
}
// 点积
db dot(P3 a, P3 b) {
    return a.x * b.x + a.y * b.y + a.z * b.z;
}
using VP = vector<P3>;
using VVP = vector<VP>;
// 点 p 与直线 k1k2 距离
db disLP(P3 k1, P3 k2, P3 p) {
    return cross(k2 - k1, p - k1).len() / (k2 - k1).len();
}
// 直线 k1k2 与 直线 k3k4 距离
db disLL(P3 k1, P3 k2, P3 k3, P3 k4) {
    P3 dir = cross(k2 - k1, k4 - k3);
    if(sgn(dir.len()) == 0) return disLP(k1, k2, k3);
    return fabs(dot(dir.unit(), k1 - k2));
}
// 平面 (p, dir) 与 直线 k1k2 的交点
VP getFL(P3 p, P3 dir, P3 k1, P3 k2) {
    db a = dot(k2 - p, dir), b = dot(k1 - p, dir);
    if(cmp(a, b) == 0) return {};
    return {(k1 * a - k2 * b) / (a- b)};
}
// 平面 (p1, dir1) 与 平面 (p2, dir2) 的交线
VP getFF(P3 p1, P3 dir1, P3 p2, P3 dir2) {
    P3 e = cross(dir1, dir2), v = cross(dir1, e); db d = dot(dir2, v);
    if(sgn(d) == 0) return {};
    P3 q = p1 + v * dot(dir2, p2 - p1) / d;
    return {q, q + e};
}
// 三维凸包
// 求 [k1k2, k1k3, k1k4] 混合积
db getV(P3 k1, P3 k2, P3 k3, P3 k4) {
    return dot(cross(k2 - k1, k3 - k1), k4 - k1);    
}
// 求指定方向上的二维凸包
VP convexHull2D(VP A, P3 dir) {
    P3 x = {rd(eng), rd(eng), rd(eng)};
    x = cross(x.unit(), dir).unit();
    P3 y = cross(x, dir).unit();
    P3 vec = dir.unit() * dot(A[0], dir);
    vector<point> B;
    for(int i = 0; i < A.size(); i++) {
        B.push_back({dot(A[i], x), dot(A[i], y)});
    }
    B = ConvexHull(B);
    A.clear();
    for(int i = 0; i < B.size(); i++) {
        A.push_back(x * B[i].x + y * B[i].y + vec);
    }
    return A;
}
namespace CH3 {
    VVP ret;
    set<pair<int, int>> e;
    int n;
    VP p, q;
    void wrap(int a, int b) {
        if(e.find({a, b}) == e.end()) {
            int c = -1;
            for(int i = 0; i < n; i++) {
                if(i != a && i != b) {
                    if(c == -1 || sgn(getV(q[c], q[a], q[b], q[i])) > 0) {
                        c = i;
                    }
                }
            }
            if(c != -1) {
                ret.push_back({p[a], p[b], p[c]});
                e.insert({a, b});
                e.insert({b, c});
                e.insert({c, a});
                wrap(c, b), wrap(a, c);
            }
        }
    }
    VVP ConvexHull3D(VP _p) {
        p = q = _p;
        n = p.size();
        ret.clear(), e.clear();
        // 扰动 lg(n) 次
        for(int t = 1; t <= 3; t++) {       
            for(auto &i : q) {
                i = i + P3{(rd(eng) - 0.5) * eps, (rd(eng) - 0.5) * eps, (rd(eng) - 0.5) * eps};
            }
        }
        for(int i = 1; i < n; i++) {
            if(cmp(q[i].x, q[0].x) == -1) {
                swap(p[0], p[i]);
                swap(q[0], q[i]);
            }
        }
        for(int i = 2; i < n; i++) {
            if(cmp((q[i].x - q[0].x) * (q[1].y - q[0].y), (q[i].y - q[0].y) * (q[1].x - q[0].x)) == 1) {
                swap(q[1], q[i]);
                swap(p[1], p[i]);
            }
        }
        wrap(0, 1);
        return ret;
    }
}
// 严格三维凸包
VVP reduceCH(VVP A){
    VVP ret; 
    map<P3,VP> M;
    for (auto nowF : A){
        P3 dir = cross(nowF[1] - nowF[0], nowF[2] - nowF[0]).unit();
        for(P3 k1 : nowF) M[dir].push_back(k1);
    }
    for (auto nowF : M) ret.push_back(convexHull2D(nowF.second, nowF.first));
    return ret;
}
// 将平面转化成点法式
pair<P3, P3> getF(VP F) {
    return {F[0], cross(F[1] - F[0], F[2] - F[0]).unit()};
}
// 平面切凸包 (保留 dir 指向的部分)
VVP ConvexCut3D(VVP A, P3 p, P3 dir) {
    VVP ret;
    VP sec;
    for(auto nowF : A) {
        int n = nowF.size();
        VP ans;
        bool dif = 0;
        for(int i = 0; i < n; i++) {
            P3 p1 = nowF[i], p2 = nowF[(i + 1) % n];
            int d1 = sgn(dot(dir, p1 - p));
            int d2 = sgn(dot(dir, p2 - p));
            if(d1 >= 0) ans.push_back(p1);
            if(d1 * d2 < 0) {
                P3 q = getFL(p, dir, p1, p2)[0];
                ans.push_back(q);
                sec.push_back(q);
            }
            if(d1 == 0) sec.push_back(p1);
            else dif = 1;
            dif |= (sgn(dot(dir, cross(p2 - p1, p2 - p1))) == -1);
        }
        if(ans.size() > 0 && dif) ret.push_back(ans);
    }
    if(sec.size() > 0) ret.push_back(convexHull2D(sec, dir));
    return ret;
}
// 多面体体积
db vol(VVP A) {
    if(A.size() == 0) return 0;
    P3 p = A[0][0];
    db ans = 0;
    for(auto nowF : A) {
        for(int i = 2; i < nowF.size(); i++) {
            ans += abs(getV(p, nowF[0], nowF[i - 1], nowF[i]));
        }
    }
    return ans / 6;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout << fixed << setprecision(10);
    int n, m;
    cin >> n >> m;
    vector<point> A(n), B(m);       
    for (int i = 0; i < n; i++) {
        cin >> A[i];
    }
    for (int i = 0; i < m; i++) {
        cin >> B[i];
    }
    vector<bool> vis(m);
    db ans = 0;
    vector<point> V;
    for (int i = 0; i < n; i++) {
        point p1 = A[i], p2 = A[(i + 1) % n];
        vector<point> v;
        for (int j = 0; j < m; j++) {
            if (sgn(cross(p2 - p1, B[j] - p1)) == 0 && inmid(B[j], p1, p2) && !vis[j]) {
                v.push_back(B[j]);
                vis[j] = true;
            }
        }
        if (v.size() == 0) {
            continue;
        }
        if (v.size() == 1) {
            V.push_back(v[0]);
            continue;
        }
        point l, r;
        db mn = 1e18, mx = -1e18;
        for (auto p : v) {
            if (cmp(dis(p, p1), mn) == -1) {
                l = p;
                mn = dis(p, p1);
            }
            if (cmp(dis(p, p1), mx) == 1) {
                r = p;
                mx = dis(p, p1);
            }
        }
        V.push_back(l), V.push_back(r);
    }
    auto check = [&] (point p1, point p2) {
        point m = (p1 + p2) / 2;
        if (contain(A, m) == 0) {
            return false;
        }
        if (contain(A, p2) == 0) {
            return false;
        }
        for (int i = 0; i < n; i++) {
            point p3 = A[i], p4 = A[(i + 1) % n];
            if (parallel({p1, p2}, {p3, p4})) {
                continue;
            }
            point d = getLL({p1, p2}, {p3, p4});
            db d1 = dis(d, p1), d2 = dis(d, p3);
         
            if (inmid(d, p1, p2) && inmid(d, p3, p4) &&
            cmp(d1, 0) == 1 && cmp(d1, dis(p1, p2)) == -1 &&
            cmp(d2, 0) == 1 && cmp(d2, dis(p3, p4)) == -1) {
                return false;
            }
        }
        return true;
    };
    vector Adj(n + 2, vector<pair<int, db>>());
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (check(A[i], A[j])) { 
                Adj[i].push_back({j, dis(A[i], A[j])});
                Adj[j].push_back({i, dis(A[i], A[j])});
            }
        }
    }
    
    for (int i = 0; i < V.size(); i++) {
        auto adj = Adj;
        point s = V[i], t = V[(i + 1) % V.size()];
        if (check(s, t)) {
            ans += dis(s, t);
            continue;
        }
        for (int j = 0; j < n; j++) {
            if (check(A[j], s)) {
                adj[j].push_back({n, dis(A[j], s)});
                adj[n].push_back({j, dis(A[j], s)});
            }
            if (check(A[j], t)) {
                adj[j].push_back({n + 1, dis(A[j], t)});
                adj[n + 1].push_back({j, dis(A[j], t)});
            }
        }
        
        vector<db> dist(n + 2, 1e18);
        dist[n] = 0;
        vector<bool> vis(n + 2);
        priority_queue<pair<db, int>, vector<pair<db, int>>, greater<pair<db, int>>> pq;
        pq.push({0, n});
        while (!pq.empty()) {
            auto [dis, x] = pq.top();
            pq.pop();
            if (vis[x]) {
                continue;
            }
            vis[x] = true;
            if (x == n + 1) {
                break;
            }  
            for (auto [y, d] : adj[x]) {
                if (dist[y] > dis + d) {
                    dist[y] = dis + d;
                    pq.push({dist[y], y});
                }
            }
        }
        ans += dist[n + 1];
    }
    cout << ans << "\n";
    return 0;
}