!ratio template

typedef long long ll;
typedef long double ld;

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

/*--------------------------------------BEGIN OF RAT----------------------------------*/

struct rat
{
    ll x, y;

    rat(ll xx, ll yy = 1)
    {
        x = xx;
        y = yy;
        if (y < 0)
        {
            x = -x;
            y = -y;
        }
    }

    rat()
    {
        x = 0;
        y = 1;
    }

    void norm()
    {
        ll t = abs(gcd(x, y));
        x /= t;
        y /= t;
    }

    ld to_ld()
    {
        return (ld)x / (ld)y;
    }

    ll to_ll()
    {
        return x / y;
    }

/*----------------------------------------cmp with rat---------------------------------*/

    bool operator<(const rat &other) const
    {
        return x * other.y < y * other.x;
    }

    bool operator>(const rat &other) const
    {
        return x * other.y > y * other.x;
    }

    bool operator<=(const rat &other) const
    {
        return x * other.y <= y * other.x;
    }

    bool operator>=(const rat &other) const
    {
        return x * other.y >= y * other.x;
    }

    bool operator==(const rat &other) const
    {
        return x * other.y == y * other.x;
    }

    bool operator!=(const rat &other) const
    {
        return x * other.y != y * other.x;
    }

/*---------------------------------------ops with rat----------------------------*/

    rat operator*(const rat &other) const
    {
        return rat(x * other.x, y * other.y);
    }

    void operator*=(const rat &other)
    {
        x *= other.x;
        y *= other.y;
    }

    rat operator/(const rat &other) const
    {
        if (other.x > 0)
            return rat(x * other.y, y * other.x);
        else
            return rat(-x * other.y, -y * other.x);
    }

    void operator/=(const rat &other)
    {
        x *= other.y;
        y *= other.x;
        if (y < 0)
        {
            y = -y;
            x = -x;
        }
    }

    rat operator+(const rat &other) const
    {
        return rat(x * other.y + y * other.x, y * other.y);
    }

    void operator+=(const rat &other)
    {
        x = x * other.y + y * other.x;
        y *= other.y;
    }

    rat operator-(const rat &other) const
    {
        return rat(x * other.y - y * other.x, y * other.y);
    }

    void operator-=(const rat &other)
    {
        x = x * other.y - y * other.x;
        y *= other.y;
    }

/*----------------------------------------cmp with ll--------------------------------*/

    bool operator<(const ll &k) const
    {
        return x < y * k;
    }

    bool operator>(const ll &k) const
    {
        return x > y * k;
    }

    bool operator<=(const ll &k) const
    {
        return x <= y * k;
    }

    bool operator>=(const ll &k) const
    {
        return x >= y * k;
    }

    bool operator==(const ll &k) const
    {
        return x == y * k;
    }

    bool operator!=(const ll &k) const
    {
        return x != y * k;
    }

/*----------------------------------------ops with ll--------------------------------*/

    rat operator*(const ll &k) const
    {
        return rat(x * k, y);
    }

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

    rat operator/(const ll &k) const
    {
        if (k > 0)
            return rat(x, y * k);
        else
            return rat(-x, -y * k);
    }

    void operator/=(const ll &k)
    {
        y *= k;
        if (y < 0)
        {
            y = -y;
            x = -x;
        }
    }

    rat operator+(const ll &k) const
    {
        return rat(x + y * k, y);
    }

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

    rat operator-(const ll &k) const
    {
        return rat(x - y * k, y);
    }

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

/*----------------------------------------cmp with ll--------------------------------*/

bool operator<(const ll &k, const rat &v)
{
    return k * v.y < v.x;
}

bool operator>(const ll &k, const rat &v)
{
    return k * v.y > v.x;
}

bool operator<=(const ll &k, const rat &v)
{
    return k * v.y <= v.x;
}

bool operator>=(const ll &k, const rat &v)
{
    return k * v.y >= v.x;
}

bool operator==(const ll &k, const rat &v)
{
    return k * v.y == v.x;
}

bool operator!=(const ll &k, const rat &v)
{
    return k * v.y != v.x;
}

/*----------------------------------------ops with ll--------------------------------*/

rat operator*(const ll &k, const rat &v)
{
    return rat(v.x * k, v.y);
}

rat operator/(const ll &k, const rat &v)
{
    if (v.x > 0)
        return rat(k * v.y, v.x);
    else
        return rat(-k * v.y, -v.x);
}

rat operator+(const ll &k, const rat &v)
{
    return rat(v.x + v.y * k, v.y);
}

rat operator-(const ll &k, const rat &v)
{
    return rat(v.y * k - v.x, v.y);
}

/*--------------------------------------END OF RAT-----------------------------------*/

/* rat(x) // x
 * rat(x, y) // x/y
 * rat() // 0/1
 * .norm() // /gcd
 * .to_ld
 * .to_ll
 * < > <= >= == != (also for ll and in reverse order)
 * * *= / /= + += - -= (also for ll and in reverse order)
 */