#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using pt=ll;
constexpr pt eps =0;
template<typename T> struct point{
    T x,y;
    bool operator==(const point &a)const{return {abs(x-a.x)<=eps&&abs(y-a.y)<=eps};}
    bool operator<(const point &a)const{if(abs(x-a.x)<=eps)return y<a.y-eps;return x<a.x-eps;}
    bool operator>(const point &a)const{return !(*this<a||*this==a);}
    point operator+(const point &a)const{return {x+a.x,y+a.y};}
    point operator-(const point &a)const{return {x-a.x,y-a.y};}
    point operator-()const{return {-x,-y};}
    point operator*(const T k)const {return {k*x,k*y};};
    T operator*(const point &a)const{return x*a.x+y*a.y;}
    T operator^(const point &a)const{return x*a.y-y*a.x;}
    int toleft(const point &a)const{const auto t=(*this)^a;return (t>eps)-(t<-eps);}
    T len2() const{return (*this)*(*this);}
};
using Point = point<ll>;
struct argcmp
{
    bool operator()(const Point &a,const Point &b)const{
        const auto quad=[](const Point &a)
        {
            if(a.y<-eps)return 1;
            if(a.y>eps)return 4;
            if(a.x<-eps)return 5;
            if(a.x>eps)return 3;
            return 2;
        };
        const int qa=quad(a),qb=quad(b);
        if(qa!=qb)return qa<qb;
        const auto t=a^b;
        return t>eps;
    }
};

template<typename T> struct line{
    point<T> p,v;
    int toleft(const point<T> &a)const{return v.toleft(a-p);}
};
using Line = line<pt>;

template<typename T> struct segment{
    point<T> a,b;
    int is_on(const point<T> &p)const{
        if(p==a||p==b)return -1;
        return (p-a).toleft(p-b)==0&& (p-a)*(p-b)<-eps;
    }
    int is_inter(const segment<T> &s)const{
        if(is_on(s.a)||is_on(s.b)||s.is_on(a)||s.is_on(b))return -1;
        const line<T> l{a,b-a},ls{s.a,s.b-s.a};
        return l.toleft(s.a)*l.toleft(s.b)==-1&&ls.toleft(a)*ls.toleft(b)==-1;
    }
};
int main()
{

}