#include <bits/stdc++.h>
using namespace std;
#define TR(i,v)         for(__typeof((v).begin())i=(v).begin();i!=(v).end();++i)
#define DEBUG(x)        cout << #x << " = " << x << endl;
#define SIZE(p)         (int)(p).size()
#define MP(a, b)        make_pair((a), (b))
#define ALL(p)          (p).begin(), (p).end()
#define rep(i, n)       for(int (i)=0; (i)<(int)(n); ++(i))
#define REP(i, a, n)    for(int (i)=(a); (i)<(int)(n); ++(i))
#define FOR(i, a, b)    for(int (i)=(int)(a); (i)<=(int)(b); ++(i))
#define FORD(i, b, a)   for(int (i)=(int)(b); (i)>=(int)(a); --(i))
#define CLR(x, y)       memset((x), (y), sizeof((x)))
typedef long long LL;
typedef pair<int, int> pii;
//平面二维几何
//Template
typedef double NUM;
const double eps = 1e-10;
const double PI = acos(-1);
const double TWO_PI = 2*PI;
inline int dcmp(NUM x)   {
    return abs(x)<eps ? 0 : x<0 ? -1 : 1;
}
inline double zero(double x) {
    return dcmp(x)==0 ? 0 : x;
}
double normalizeAngle(double rad, double center = PI) {     //将角度标准化到区间 [center-PI,center+PI)
    return rad-TWO_PI*floor((rad+PI-center)/TWO_PI);
}
struct Point {
    NUM x, y;
    Point(NUM xx=0, NUM yy=0):    x(xx), y(yy)    {}
    void read() {cin>>x>>y;}
    void print() {cout<<fixed<<setprecision(12)<<x<<" "<<y;}
};
typedef Point Vector;
typedef vector<Point> Polygon;
Vector operator+(Vector A, Vector B)        {return Vector(A.x+B.x, A.y+B.y);}
Vector operator-(Point A, Point B)          {return Vector(A.x-B.x, A.y-B.y);}
Vector operator*(Vector A, NUM p)           {return Vector(A.x*p, A.y*p);}
Vector operator/(Vector A, NUM p)           {return Vector(A.x/p, A.y/p);}
bool operator<(const Point &a, const Point &b) {
    return dcmp(a.x-b.x)<0 || (dcmp(a.x-b.x)==0 && dcmp(a.y-b.y)<0);
}
bool operator == (const Point a, const Point b) {
    return dcmp(a.x-b.x)==0 && dcmp(a.y-b.y)==0;
}

NUM Dot(Vector A, Vector B)                 {return A.x*B.x + A.y*B.y;}                     //计算两个向量之间的点积
double Length(Vector A)                     {return sqrt(Dot(A,A));}                        //计算向量的模
double Angle(Vector A, Vector B)            {return acos(Dot(A,B)/Length(A)/Length(B));}    //计算两个向量之间的夹角
NUM Cross(Vector A, Vector B)               {return A.x*B.y - A.y*B.x;}                     //计算两个向量之间的叉积
NUM Area2(Point A, Point B, Point C)        {return Cross(B-A,C-A);}                        //计算三角形A,B,C的有向面积
double angle(Vector v)                      {return atan2(v.y, v.x);}                       //计算向量的极角
double torad(double deg)                       {return deg/180.0*PI;}                       //角度转化为弧度
Vector Rotate(Vector A, double rad) {                                                       //向量逆时针旋转rad    
    return Vector(A.x*cos(rad)-A.y*sin(rad), A.x*sin(rad)+A.y*cos(rad));
}
Vector Normal(Vector A) {           //计算向量的单位法向量(确保A不是零向量)
    double L=Length(A);
    return Vector(-A.y/L, A.x/L);
}

struct Line {
    Point p;
    Vector v;
    double ang;
    Line()  {}
    Line(Point p, Vector v):p(p),v(v) {ang=atan2(v.y,v.x);}
    Point point(double t) {
        return p+v*t;
    }
    Line move(double d) {
        return Line(p+Normal(v)*d, v);
    }
    bool operator<(Line L) const {
        return dcmp(ang-L.ang)<0;
    }
    static Line getLine(double x1, double y1, double x2, double y2) {
        Point a=Point(x1,y1);
        Point b=Point(x2,y2);
        return Line(a, b-a);
    }
};
Point getLineIntersection(Point P, Vector v, Point Q, Vector w) {   //计算两个直线(P,v)和(Q,w)之间的交点
    Vector u=P-Q;
    double t=Cross(w,u)/Cross(v,w);
    return P+v*t;
}
double distanceToLine(Point P, Point A, Point B) {                  //计算点P到直线AB之间的距离(绝对值)
    Vector v1=B-A, v2=P-A;
    return abs(Cross(v1,v2))/Length(v1);
}
double distanceToSegment(Point P, Point A, Point B) {               //计算点P到线段AB之间的距离(绝对值)
    if(A == B)      return Length(P-A);
    Vector v1=B-A, v2=P-A, v3=P-B;
    if(dcmp(Dot(v1,v2)) < 0)            return Length(v2);
    if(dcmp(Dot(v1,v3)) > 0)            return Length(v3);
    return abs(Cross(v1,v2))/Length(v1);
}
Point getLineProjection(Point P, Point A, Point B) {                //计算点P在直线AB上的投影点
    Vector v=B-A;
    return A+v*(Dot(v, P-A)/Dot(v, v));
}
Point getLineProjection(Point P, Line Q) {                          //计算点P在直线Q上的投影点
    return Q.p+Q.v*(Dot(Q.v,P-Q.p)/Dot(Q.v,Q.v));
}
bool segmentProperIntersection(Point a1, Point a2, Point b1, Point b2) {    //判断两个线段(a1,a2)和(b1,b2)是否规范相交
    NUM c1=Cross(a2-a1, b1-a1), c2=Cross(a2-a1, b2-a1);
    NUM c3=Cross(b2-b1, a1-b1), c4=Cross(b2-b1, a2-b1);
    return dcmp(c1)*dcmp(c2) < 0 && dcmp(c3)*dcmp(c4) < 0;
}
bool onSegment(Point P, Point a1, Point a2) {                           //判断点P是否在线段(a1,a2)上(不包含端点)
    return dcmp(Cross(a1-P, a2-P)) == 0 && dcmp(Dot(a1-P, a2-P)) < 0;
}
void getLineGeneralEquation(const Point& p1, const Point& p2, double& a, double& b, double &c) {    //直线两点式求一般式方程
  a=p2.y-p1.y;
  b=p1.x-p2.x;
  c=-a*p1.x - b*p1.y;
}

//圆相关部分
struct Circle {
    Point c;
    NUM r;
    Circle()    {}
    Circle(Point c, NUM r):c(c),r(r) {}
    Point point(double a) {
        return Point(c.x+cos(a)*r, c.y+sin(a)*r);
    }
    void read() {cin>>c.x>>c.y>>r;}        
};
int getLineCircleIntersection(Line L, Circle C, double& t1, double& t2, vector<Point>& sol) {   //计算直线L与圆C的交点,返回交点个数
    NUM a = L.v.x, b = L.p.x - C.c.x, c = L.v.y, d = L.p.y - C.c.y;                          //交点保存在sol中，注意不会清空sol
    NUM e = a*a + c*c, f = 2*(a*b + c*d), g = b*b + d*d - C.r*C.r;                           //t1,t2是返回的参数方程中交点对应的参数，顺序和sol中相同
    NUM delta = f*f - 4*e*g; // 判别式
    if (dcmp(delta) < 0) return 0; // 相离
    if (dcmp(delta) == 0) { // 相切
        t1 = t2 = -f / (2 * e);
        sol.push_back(L.point(t1));
        return 1;
    }
    // 相交
    t1 = (-f - sqrt(delta)) / (2 * e);
    sol.push_back(L.point(t1));
    t2 = (-f + sqrt(delta)) / (2 * e);
    sol.push_back(L.point(t2));
    return 2;
}
int getCircleCircleIntersection(Circle C1, Circle C2, vector<Point>& sol) {                 //计算圆C1和C2的交点，保存在sol中，返回交点的个数
    double d = Length(C1.c - C2.c);
    if (dcmp(d) == 0) {
        if (dcmp(C1.r - C2.r) == 0) return -1; // 重合，无穷多交点
        return 0;
    }
    if (dcmp(C1.r + C2.r - d) < 0) return 0;
    if (dcmp(fabs(C1.r-C2.r) - d) > 0) return 0;

    double a = angle(C2.c - C1.c);
    double da = acos((C1.r*C1.r + d*d - C2.r*C2.r) / (2*C1.r*d));
    Point p1 = C1.point(a-da), p2 = C1.point(a+da);

    sol.push_back(p1);
    if (p1 == p2) return 1;
    sol.push_back(p2);
    return 2;
}
int getCircleCircleIntersection(Circle C1, Circle C2, vector<double> &sol) {        // 两圆相交求交点
    double d = Length(C1.c-C2.c);                                                   // 交点相对于圆1的极角保存在rad中
    if (dcmp(d) == 0) {
        if (dcmp(C1.r - C2.r) == 0) return -1; // 重合，无穷多交点
        return 0;
    }
    if (dcmp(C1.r + C2.r - d) < 0) return 0;
    if (dcmp(fabs(C1.r-C2.r) - d) > 0) return 0;

    double a = angle(C2.c - C1.c);
    double da = acos((C1.r*C1.r + d*d - C2.r*C2.r) / (2*C1.r*d));    
    double ra = normalizeAngle(a-da), rb = normalizeAngle(a+da);
    sol.push_back(ra);
    if(dcmp(ra-rb) == 0)        return 1;
    sol.push_back(rb);
    return 2;
}
int getTangents(Point p, Circle C, vector<Vector> &sol) {       // 计算点到圆的切线
    Vector u = C.c - p;                                         // 过点p到圆C的切线。sol[i]是第i条切线的向量。返回切线条数
    double dist = Length(u);                                    // 切线向量保存在sol中  
    if (dist < C.r) return 0;
    else if (dcmp(dist - C.r) == 0) { // p在圆上，只有一条切线        
        sol.push_back(Rotate(u, PI/2));
        return 1;
    } else {
        double ang = asin(C.r / dist);        
        sol.push_back(Rotate(u, -ang));
        sol.push_back(Rotate(u, +ang));
        return 2;
    }
}
int getTangents(Circle A, Circle B, vector<Point> &a, vector<Point> &b){        //计算两圆的公切线，返回切线数量, 公切线与圆A、B的切点保存在a[i],b[i]中
    int cnt = 0;        //存切点用
    if(dcmp(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(dcmp(d - rdiff) < 0) return 0;        //1.内含
    double base = atan2(B.c.y - A.c.y, B.c.x - A.c.x);      //向量AB的极角
    if(dcmp(d) == 0) return -1;        //2.重合
    if(dcmp(d - rdiff) == 0) {       //3.内切
        Point tp = A.point(base);
        a.push_back(tp), b.push_back(tp);
        cnt++;
        return 1;
    }
    double ang = acos((A.r - B.r) / d);
    a.push_back(A.point(base + ang)); b.push_back(B.point(base + ang)); cnt++;      //4.相交（外切、外离的外公切线也在此求出）
    a.push_back(A.point(base - ang)); b.push_back(B.point(base - ang)); cnt++;      //两条外公切线的切点
    if(dcmp(d - rsum) == 0) {        //5.外切
        Point tp = A.point(base);
        a.push_back(tp), b.push_back(tp);
        cnt++;
    }
    else if(dcmp(d - rsum) > 0) {      //6.外离
        double ang = acos((A.r + B.r) / d);
        a.push_back(A.point(base + ang)); b.push_back(B.point(PI + base + ang)); cnt++;
        a.push_back(A.point(base - ang)); b.push_back(B.point(PI + base - ang)); cnt++;
    }
    return cnt;
}
Circle circumscribedCircle(Point p1, Point p2, Point p3) {      //计算三角形的外接圆,调用前要确保三点不共线     
    double Bx = p2.x-p1.x, By = p2.y-p1.y;
    double Cx = p3.x-p1.x, Cy = p3.y-p1.y;
    double D = 2*(Bx*Cy-By*Cx);
    double cx = (Cy*(Bx*Bx+By*By) - By*(Cx*Cx+Cy*Cy))/D + p1.x;
    double cy = (Bx*(Cx*Cx+Cy*Cy) - Cx*(Bx*Bx+By*By))/D + p1.y;
    Point p = Point(cx, cy);
    return Circle(p, Length(p1-p));
}
Circle InscribedCircle(Point p1, Point p2, Point p3) {          //计算三角形的内切圆,调用前要确保三点不共线
    double a = Length(p2-p3);
    double b = Length(p3-p1);
    double c = Length(p1-p2);
    Point p = (p1*a+p2*b+p3*c)/(a+b+c);
    return Circle(p, distanceToLine(p, p1, p2));
}
void getCoord(double R, double lat, double lng, double &x, double &y, double &z) {  //经纬度(角度)转化为三维空间坐标(x,y,z)
    lat = torad(lat), lng = torad(lng);
    x = R*cos(lat)*cos(lng);
    y = R*cos(lat)*sin(lng);
    z = R*sin(lat);
}

//多边形与凸包相关
int isPointInPolygon(Point p, vector<Point> &v) {         //判断点p与多边形v的位置关系,多边形可以自交
    int wn = 0;
    int n = v.size();
    for (int i = 0; i < n; i++) {
        if (p == v[i] || p == v[(i+1)%n] || onSegment(p, v[i], v[(i+1)%n])) return -1; // 在边界上
        int k = dcmp(Cross(v[(i+1)%n]-v[i], p-v[i]));
        int d1 = dcmp(v[i].y - p.y);
        int d2 = dcmp(v[(i+1)%n].y - p.y);
        if (k > 0 && d1 <= 0 && d2 > 0) wn++;
        if (k < 0 && d2 <= 0 && d1 > 0) wn--;
    }
    if (wn != 0) return 1; // 内部
    return 0; // 外部
}
vector<Point> convexHull(vector<Point> p) {           // 计算点集的凸包
    // 预处理，删除重复点                             // 如果不希望在凸包的边上有输入点，把两个 <= 改成 <
    sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end()), p.end());

    int n = p.size(), m = 0;    
    vector<Point> ch(n+1);
    for (int i = 0; i < n; i++) {
        while (m > 1 && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) <= 0) m--;
        ch[m++] = p[i];
    }
    int k = m;
    for (int i = n-2; i >= 0; i--) {
        while (m > k && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) <= 0) m--;
        ch[m++] = p[i];
    }
    if (n > 1) m--;
    ch.resize(m);
    return ch;
}
double polygonArea(vector<Point> &p) {          //计算多边形的有向面积
    int n=p.size();
    double area=0;
    for (int i=1;i<n-1;i++)
        area+=Cross(p[i]-p[0], p[i+1]-p[0]);
    return area/2;
}

//半平面交
inline bool onLeft(const Line& L, const Point& p) {         //点p在有向直线L的左边(不包括在线上)
    return Cross(L.v, p-L.p) > 0;
}
Point getLineIntersection(Line a, Line b) {                         //计算两个直线a和b之间的交点
    return getLineIntersection(a.p, a.v, b.p, b.v);
}
vector<Point> halfplaneIntersection(vector<Line> L) {       // 半平面交主过程
    int n = L.size();
    sort(L.begin(), L.end()); // 按极角排序

    int first, last;         // 双端队列的第一个元素和最后一个元素的下标
    vector<Point> p(n);      // p[i]为q[i]和q[i+1]的交点
    vector<Line> q(n);       // 双端队列
    vector<Point> ans;       // 结果

    q[first=last=0] = L[0];  // 双端队列初始化为只有一个半平面L[0]
    for (int i = 1; i < n; i++) {
        while (first < last && !onLeft(L[i], p[last-1])) last--;
        while (first < last && !onLeft(L[i], p[first])) first++;
        q[++last] = L[i];
        if (fabs(Cross(q[last].v, q[last-1].v)) < eps) { // 两向量平行且同向，取内侧的一个
            last--;
            if (onLeft(q[last], L[i].p)) q[last] = L[i];
        }
        if (first < last) p[last-1] = getLineIntersection(q[last-1], q[last]);
    }
    while (first < last && !onLeft(q[first], p[last-1])) last--; // 删除无用平面
    if (last - first <= 1) return ans; // 空集
    p[last] = getLineIntersection(q[last], q[first]); // 计算首尾两个半平面的交点

    // 从deque复制到输出中
    for (int i = first; i <= last; i++) ans.push_back(p[i]);
    return ans;
}
Polygon cutPolygon(const Polygon &P, Point A, Point B) {
    int n=P.size();
    Polygon newP;
    for(int i=0;i<n;++i) {
        Point C=P[i], D=P[i+1==n?0:i+1];
        if(dcmp(Cross(B-A,C-A)) >= 0)   newP.push_back(C);
        if(dcmp(Cross(B-A,D-C)) != 0) {
            Point E=getLineIntersection(A,B-A,C,D-C);
            if(onSegment(E,C,D))        newP.push_back(E);
        }
    }
    return newP;
}
int main(int argc, char const *argv[]) {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    // freopen("out", "w", stdout);
#endif
    // ios::sync_with_stdio(false);		cin.tie(0);
    
    return 0;
}