!Integer Geometry

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


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

struct Point
{
    ll x, y;

    Point():
        x(0),
        y(0) {}
    Point(ll x, ll 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;
    }

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

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

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

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

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

    ll lensqr() const
    {
        return x * x + y * y;
    }

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

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

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

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

    Point operator=(const Point &a)
    {
        x = a.x;
        y = a.y;
        return (*this);
    }

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

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

    void debwrite() const
    {
#ifdef ONPC
        cerr << "       point: x = " << x << ", y = " << y << endl;
#endif
    }

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

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

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

ll distsqr(const Point &a, const Point &b)
{
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}



ll gcd(ll a, ll b)
{
    while (a)
    {
        b %= a;
        swap(a, b);
    }
    return b;
}


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


struct Line
{
    ll a, b, c;

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

    Line(ll a, ll b, ll 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) {}

    ll lensqr() const
    {
        return a * a + b * b;
    }

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

    void norm()
    {
#ifdef ONPC
        if (a == 0 && b == 0)
            assert("norming strange (0, 0, c) line");
#endif
        ll x = gcd(a, gcd(b, c));
        a /= x;
        b /= x;
        c /= x;
        if (a < 0 || (a == 0 && b < 0))
        {
            a = -a;
            b = -b;
            c = -c;
        }
    }

    bool parallel(const Line &l) const
    {
        return l.a * b == l.b * a;
    }

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

    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() const
    {
#ifdef ONPC
        cerr << "       line: a = " << a << ", b = " << b << ", c = " << c << endl;
#endif
    }

};

bool parallel(Line l, Line k)
{
    return l.a * k.b == l.b * k.a;
}

bool point_on_line(Point p, Line l)
{
    return p.x * l.a + p.y * l.b + l.c == 0;
}

bool point_on_line(Point p, Point a, Point b)
{
    return point_on_line(p, Line(a, b));
}

bool point_on_line(Line l, Point p)
{
    return p.x * l.a + p.y * l.b + l.c == 0;
}

bool three_points_on_line(Point a, Point b, Point c)
{
    return ((a - b) ^ (b - c)) == 0;
}

bool collinear(Point a, Point b, Point c)
{
    return ((a - b) ^ (b - c)) == 0;
}

Line perp(Point p, Line l)
{
    return Line(-l.b, l.a, p.x * l.b - p.y * l.a);
}

Line perp(Line l, Point p)
{
    return Line(-l.b, l.a, p.x * l.b - p.y * l.a);
}

bool point_on_ray(Point p, Point a, Point b)
{
    if ((b - a) * (p - a) >= 0)
    {
        Line l(a, b);
        return point_on_line(p, l);
    }
    return 0;
}

bool point_on_segment(Point p, Point a, Point b)
{
    return point_on_ray(p, a, b) && point_on_ray(p, b, a);
}

bool point_in_angle(Point P, Point A, Point O, Point B)
{
    P -= O;
    A -= O;
    B -= O;
    if ((B ^ A) > 0)
        swap(A, B);
    return (A ^ P) >= 0 && (P ^ B) >= 0;
}

ll double_area(vector<Point> p)
{
    ll 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 abs(s);
}

bool point_in_convex_polygon(Point A, 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]);
        if (l(A) * l(p[k]) < 0)
            return 0;
    }
    return 1;
}


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

bool convex_hull_cmp(Point v, Point u)
{
    if (u.is_zero())
        return 0;
    if (v.is_zero())
        return 1;
    bool x = where(v), y = where(u);
    if (x != y)
        return x;
    ll t = (v ^ u);
    if (t != 0)
        return t > 0;
    return v.lensqr() < u.lensqr();
}

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 && ((a[i] - v.back()) ^ (v.back() - v[v.size() - 2])) >= 0)
            v.pop_back();
        v.push_back(a[i]);
    }
    for (int i = 0; i < (int)v.size(); i++)
        v[i] += down;
    return v;
}

vector<Point> jarvis_convex_hull(vector<Point> a)
{
    int n = a.size();
    if (n < 2)
        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 || ((a[i] - a[cur]) ^ (a[next] - a[cur])) > 0 ||
            (((a[i] - a[cur]) ^ (a[next] - a[cur])) == 0 && (a[i] - a[cur]).lensqr() > (a[next] - a[cur]).lensqr())))
                next = i;
        if (next == k)
            break;
        v.push_back(a[next]);
        cur = next;
    }
    return v;
}

vector<Point> sum(vector<Point> a, 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 < (int)vect.size(); i++)
    {
        start += vect[i];
        v.push_back(start);
    }
    return v;
}

bool ray_ray_intersect(Point x, Point y, Point p, Point q)
{
    if (point_on_ray(x, p, q) || point_on_ray(y, p, q) || point_on_ray(p, x, y) || point_on_ray(q, x, y))
        return true;
    if (point_on_line(x, p, q) || point_on_line(y, p, q))
        return false;
    Line l(x, y), k(p, q);
    if (parallel(l, k))
        return false;
    ll a = k.c * l.b - l.c * k.b;
    ll b = l.a * k.b - k.a * l.b;
    ll c = k.a * l.c - l.a * k.c;
    ll d = b;
    if (b < 0)
    {
        a = -a;
        b = -b;
        c = -c;
        d = -d;
    }
    y -= x;
    q -= p;
    bool A = 1, B = 1, C = 1, D = 1;
    if (y.x < 0 || (y.x == 0 && y.y < 0))
        A = 0;
    if (q.x < 0 || (q.x == 0 && q.y < 0))
        C = 0;
    if (a < b * x.x || (a == b * x.x && c < d * x.y))
        B = 0;
    if (a < b * p.x || (a == b * p.x && c < d * p.y))
        D = 0;
    bool fir = (A == B), sec = (C == D);
    return fir && sec;
}

bool rays_intersect(Point x, Point y, Point p, Point q)
{
    return ray_ray_intersect(x, y, p, q);
}

bool segment_ray_intersect(Point x, Point y, Point p, Point q)
{
    return ray_ray_intersect(x, y, p, q) && ray_ray_intersect(y, x, p, q);
}

bool ray_segment_intersect(Point p, Point q, Point x, Point y)
{
    return segment_ray_intersect(x, y, p, q);
}

bool segment_segment_intersect(Point x, Point y, Point p, Point q)
{
    return segment_ray_intersect(x, y, p, q) && segment_ray_intersect(x, y, q, p);
}

bool segments_intersect(Point x, Point y, Point p, Point q)
{
    return segment_segment_intersect(x, y, p, q);
}

/*                     Functions:
 *
 * sqr(ll a) = a^2
 * distsqr(Point a, Point b) = d(a, b)^2
 * gcd(a, b)
 *
 *
 *                     Points:
 * Point() = (0, 0)
 * Point(x, y) = (x, y)
 * -Point
 * Point + Point
 * Point += Point
 * Point - Point
 * Point -= Point
 * Point ^ Point = vect product
 * Point * Point = scal product
 * Point * ll
 * ll * Point
 * Point *= ll
 * lensqr() == len of vector
 * operator<
 * operator>
 * operator==
 * operator!=
 * operator=
 * read (x, y)
 * write (x y\n)
 * debwrite cerr (         point: x = ..., y = ...endl)
 * rotate (-y, x)
 * is_zero (0, 0)?
 *
 *
 *
 *                  Lines:
 * Line() = (1, 1, 0)
 * Line(a, b, c) = (a, b, c)
 * Line(Point a, Point b) = a, b on line
 * lensqr() = a * a + b * b
 * operator()(Point) = ax + by + c
 * norm = /=gcd. equal lines are now equal. assertion ifdef ONPC
 * parallel(line) = parallel or equal
 * lies(Point)
 * perpendicular() = (-b, a, 0)
 * perpendicular(Point) = (-b, a, bx - ay)
 * read (a, b, c)
 * write (a b c\n)
 * debwrite cerr (       line: a = ..., b = ..., c = ...endl)
 *
 *
 *                 Standart:
 * parallel(Line, Line) = parallel or equal
 * point_on_line(Point, Line) or (Line, Point)
 * three_points_on_line = collinear(a, b, c)
 * perp(Line, Point) or (Point, Line) = Line.perpendicular(Point)
 * point_on_ray(p, l, r) = not strictly
 * point_on_segment(p, l, r) = not strictly
 * point_in_angle(p, a, o, b) = not strictly
 * double_area(vector<Point>) = sqr * 2 (sqr can be not int)
 * point_in_convex_polygon(Point, vector<Point>) = not strictly
 * graham_convex_hull = no collinear points
 * jarvis_convex_hull = no collinear points
 * sum(vector<Point>, vector<Point>) = sum of polygons
 * bool segment_ray_intersect(x, y, p, q) = [x, y], [p, q) ????????
 * bool ray_segment_intersect(p, q, x, y) = [x, y], [p, q) ????????
 * segment_segment_intersect = segments_intersect(x, y, p, q) = [x, y], [p, q]
 *
 *
 */

///ADD ostream, istream, ray_ray_intersect