/// https://cses.fi/problemset/task/2192/
#include 
using namespace std;
const long long INF = 3e9;
struct P{
    long long x, y;
    void read(){cin>>x>>y;};
    P operator - (P b)
    {
        return {x-b.x,y-b.y};
    }
    void operator -= (P b)
    {
        x -= b.x;
        y -= b.y;
    }
    long long operator * (P b)
    {
        return (1LL*x*b.y) - (1LL*y*b.x) ;
    }
    long long triangle (P b , P c)
    {
        return (b - *this) * (c - *this);
    }
}v[1001];
bool intersectSegment(P p1, P p2, P p3, P p4)
{
    /// If parrallel
    if((p2-p1) * (p4-p3) == 0)
    {
        if(p1.triangle(p2,p3) != 0)
            return false;
        for(int i = 1;i<=2;i++)
        {
            if((max(p1.x,p2.x) < min(p3.x,p4.x)) || (max(p1.y,p2.y) < min(p3.y,p4.y)))
                return false;
            swap(p1,p3); swap(p2,p4);
        }
        return true;
    }
    ///Not parrallel
    for(int i = 1;i<=2;i++)
    {
        long long sign1 = p1.triangle(p2,p3);
        long long sign2 = p1.triangle(p2,p4);
        if((sign1<0&&sign2<0) || (sign1>0&&sign2>0))
            return false;
        swap(p1,p3); swap(p2,p4);
    }
    return true;
}
bool segment_contains(P a, P b, P c)
{
    if(a.triangle(b,c) != 0) return false;
    return (min(a.x,b.x) <= c.x && c.x <= max(a.x,b.x))  &&
           (min(a.y,b.y) <= c.y && c.y <= max(a.y,b.y)) ;
}
int main()
{
    int n , m ;
    cin>>n>>m;
    for(int i = 0;i