#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <stdexcept>

class BigInteger;

bool operator==(const BigInteger& a, const BigInteger& b);

bool operator<(const BigInteger& a, const BigInteger& b);

bool operator!=(const BigInteger& a, const BigInteger& b);

bool operator>(const BigInteger& a, const BigInteger& b);

bool operator<=(const BigInteger& a, const BigInteger& b);

bool operator>=(const BigInteger& a, const BigInteger& b);

BigInteger operator+(const BigInteger& a, const BigInteger& b);

BigInteger operator-(const BigInteger& a, const BigInteger& b);

BigInteger operator*(const BigInteger& a, const BigInteger& b);

BigInteger operator/(const BigInteger& a, const BigInteger& b);

BigInteger operator%(const BigInteger& a, const BigInteger& b);

class BigInteger {
private:
    static const int calc_system = 1e9; //система счисления
    const int calc = 9; /// потому что в каждом digit число имеет не более 8 разрядов
    std::vector<long long> digits; //массив цифр в разрядах в обратном порядке
    bool is_positive; //положительное ли число? 0 считаем положительным
    static int stringIntCast(const std::string& s) { //строку в int
        int res = 0, ten = 1;
        for (int i = s.size() - 1; i >= 0; --i) {
            res += (s[i] - '0') * ten;
            ten *= 10;
        }
        return res;
    }
    static int how_many_digits(const int number) {
        int power_of_ten = 1, scr_of_digits = 0;
        while (number / power_of_ten != 0) {
            power_of_ten *= 10;
            ++scr_of_digits;
        }
        return  scr_of_digits;
    }
    void delete_nulls() {
        if (digits.size() == 0) {
            return;
        }
        size_t i = digits.size() - 1;
        while (digits[i] == 0) {
            i--;
            digits.pop_back();
            if (i + 1 == 0) {
                break;
            }
        }
    }
public:
    BigInteger() = default;
    BigInteger(const std::string& s) { ///случай пустой строки
        int check = 0;
        if (s[0] == '-') {
            is_positive = false;
            check = 1;
        }
        else {
            is_positive = true;
        }
        int size = s.size();
        int i = std::max(check, size - calc); ///точка, откуда мы начинаем считывание
        do {
            std::string temp_s = s.substr(i, std::min(calc, size - check));
            int temp = stringIntCast(temp_s);
            digits.push_back(temp);
            i -= calc;
            if (i + calc > check && i < check) {
                std::string temp2_s = s.substr(check, i + calc - check);
                int temp2 = stringIntCast(temp2_s);
                digits.push_back(temp2);
            }
        } while(i >= check);
    }
    BigInteger(const int a) {
        int copy = a;
        if (copy < 0) {
            is_positive = false;
            copy *= -1;
        } else {
            is_positive = true;
        }
        while (copy != 0) { ///0 представляется как ничего
            digits.push_back(copy % calc_system);
            copy /= calc_system;
        }
    }

    BigInteger& operator=(const BigInteger& a) {
        digits = a.digits;
        is_positive = a.is_positive;
        return *this;
    }

    explicit operator bool() const { ///оператор преобразования
        return (is_positive && (*this != 0));
    }

    BigInteger& operator+=(const BigInteger& a);
    BigInteger& operator-=(const BigInteger& a);
    BigInteger& operator*=(const BigInteger& a);
    BigInteger& operator/=(const BigInteger& a);
    BigInteger& operator%=(const BigInteger& a);

    std::string toString() const {
        std::string s;
        if (digits.size() == 0) {
            s = "0";
        } else {
            if (!is_positive) {
                s.push_back('-');
            }
            for (size_t i = digits.size() - 1; i + 1 != 0; --i) {
                if (digits[i] != 0) {
                    std::string temp_s = std::to_string(digits[i]);
                    s += temp_s;
                }
                if (i != 0) {
                    for (int k = 1; k <= calc - how_many_digits(digits[i - 1]); ++k) {
                        s += "0";
                    }
                }
            }
        }
        return s;
    }

    friend std::istream& operator>>(std::istream&, BigInteger&);
    friend bool operator==(const BigInteger&, const BigInteger&);
    friend bool operator<(const BigInteger&, const BigInteger&);
    BigInteger& operator++() { ///префиксный ++i
        *this += 1;
        return *this;
    }
    BigInteger operator++(int) { ///постфиксный i++
        BigInteger copy = *this;
        *this += 1;
        return copy;
    }
    BigInteger operator--() { ///--i
        *this -= 1;
        return *this;
    }
    BigInteger operator--(int) { ///i--
        BigInteger copy = *this;
        *this -= 1;
        return copy;
    }
    BigInteger operator-() const {
        BigInteger copy = *this;
        copy.is_positive = !is_positive;
        return copy;
    }

    BigInteger sign() const {
        if (is_positive) {
            return 1;
        }
        return -1;
    }
};

std::istream& operator>>(std::istream& in, BigInteger& a) {
    std::string temp_s;
    in >> temp_s;
    a = BigInteger(temp_s);
    return in;
}
std::ostream& operator<<(std::ostream& out, BigInteger a) {
    out << a.toString();
    return out;
}

bool operator==(const BigInteger& a, const BigInteger& b) {
    if (a.is_positive != b.is_positive) {
        return false;
    } else {
        size_t size_a = a.digits.size();
        size_t size_b = b.digits.size();
        if (size_a != size_b) {
            return false;
        } else {
            for (size_t i = 0; i < size_a; ++i) {
                if (a.digits[i] != b.digits[i]) {
                    return false;
                }
            }
            return true;
        }
    }
}
bool operator<(const BigInteger& a, const BigInteger& b) {
    if (a.is_positive == b.is_positive) {
        size_t size_a = a.digits.size(), size_b = b.digits.size();
        if (size_a == size_b) {
            for (size_t i = size_a - 1; i + 1 != 0; --i) {
                if (a.digits[i] > b.digits[i]) {
                    return false;
                }
                if (a.digits[i] < b.digits[i]) {
                    return true;
                }
            }
            return false;
        } else {
            return !(size_a > size_b);
        }
    } else {
        return !a.is_positive;
    }
}
bool operator!=(const BigInteger& a, const BigInteger& b) {
    return !(a==b);
}
bool operator>(const BigInteger& a, const BigInteger& b) {
    return b < a;
}
bool operator<=(const BigInteger& a, const BigInteger& b) {
    return a < b || a == b;
}
bool operator>=(const BigInteger& a, const BigInteger& b) {
    return b <= a;
}

BigInteger& BigInteger::operator-=(const BigInteger &a) {
    if (is_positive && a.is_positive) {
        if (*this >= a) {
            for (size_t i = 0; i < a.digits.size(); ++i) {
                digits[i] = digits[i] - a.digits[i];
                if (digits[i] < 0) {
                    --digits[i + 1];
                    digits[i] += calc_system;
                }
            }
            size_t last_num = digits.size() - 1;
            if (digits.size() == 0) {
                last_num = 0;
            }
            for (size_t i = 0; i < last_num; ++i) {
                if (digits[i] < 0) {
                    --digits[i + 1];
                    digits[i] += calc_system;
                }
            }
            delete_nulls();
        } else {
            BigInteger copy = a;
            copy -= *this;
            *this = copy;
            is_positive = false;
        }
    } else if (is_positive && !a.is_positive) {
        *this += -a;
    } else if (!is_positive && !a.is_positive) {
        BigInteger copy = -a;
        is_positive = true;
        copy -= *this;
        *this = copy;
    } else if (!is_positive && a.is_positive) {
        is_positive = true;
        *this += a;
        is_positive = false;
    }
    return *this;
}

BigInteger& BigInteger::operator+=(const BigInteger &a) {
    if (is_positive && a.is_positive) {
        size_t size = digits.size(), size_a = a.digits.size();
        size_t delta_size = size_a - size;
        if (size > size_a) {
            delta_size = 0;
        }
        for (size_t i = 1; i <= delta_size + 1; ++i) { ///решаем проблему с нулями
            digits.push_back(0);
        }
        //digits.push_back(0); ///потому что при сложении может вылезти на один разряд (на один ли)
        for (size_t i = 0; i < size_a; ++i) {
            digits[i+1] += (digits[i] + a.digits[i]) / calc_system;
            digits[i] = (digits[i] + a.digits[i]) % calc_system;
        }
        for (size_t i = size_a; i < digits.size() - 1; ++i) { /// -1 тут тк мы прибавили 0 для переходного разряда
            digits[i+1] += digits[i] / calc_system;
            digits[i] = digits[i] % calc_system;
        }
        delete_nulls();
    }
    if (!is_positive && !a.is_positive) {
        is_positive = true;
        *this += -a;
        is_positive = false;
    }
    if (!is_positive && a.is_positive) {
        BigInteger copy = a;
        is_positive = true;
        copy -= *this;
        *this = copy;
    }
    if (is_positive && !a.is_positive) {
        *this -= -a;
    }
    return *this;
}

BigInteger& BigInteger::operator*=(const BigInteger& a) {
    if (a == 0) {
        is_positive = true;
        return (*this = 0);
    }
    size_t size_a = a.digits.size(), my_start_size = digits.size();
    for (size_t i = my_start_size; i < my_start_size + size_a - 1; ++i) {
        digits.push_back(0);
    }
    for (size_t i = digits.size() - 1; i + 1 != 0; --i) {
        long long start_val = digits[i];
        for (size_t j_my = std::min(i, my_start_size); j_my + 1 != 0; --j_my) {
            size_t j_a = i - j_my;
            if (j_a == size_a) {
                break;
            }
            digits[i] += digits[j_my] * a.digits[j_a];
            size_t k = i;
            while (digits[k] >= calc_system) {
                if (k == digits.size() - 1) {
                    digits.push_back(0);
                }
                int carry = digits[k] / calc_system;
                digits[k] %= calc_system;
                ++k;
                digits[k] += carry;
            }
        }
        digits[i] -= start_val;
    }
    size_t last_num = digits.size() - 1;
    if (digits.size() == 0) {
        last_num = 0;
    }
    for (size_t i = 0; i < last_num; ++i) {
        if (digits[i] >= 0) {
            int carry = digits[i] / calc_system;
            digits[i] %= calc_system;
            digits[i + 1] += carry;
        } else {
            digits[i] += calc_system;
            --digits[i + 1];
        }
    }
    delete_nulls();
    is_positive = (is_positive == a.is_positive);
    return *this;
}

BigInteger &BigInteger::operator/=(const BigInteger &div_number) {
    BigInteger copy_div = div_number;
    bool start_sign = is_positive;
    is_positive = true, copy_div.is_positive = true; ///чтобы при сравнении не было проблем со знаками
    BigInteger current_div(0); //текущее делимое
    BigInteger quotient(0); //частное
    for (size_t i = digits.size(); i + 1 != 0; --i) {
        int left_pos = 0;
        int right_pos = calc_system;
        while (left_pos + 1 != right_pos) {
            int middle = (left_pos + right_pos) >> 1;
            if (middle * copy_div <= current_div) {
                left_pos= middle;
            } else {
                right_pos = middle;
            }
        }
        quotient.digits.push_back(left_pos);
        current_div -= (left_pos * copy_div);
        if (i > 0) {
            current_div = digits[i - 1] + calc_system * current_div;
        }
    }
    size_t last_num = quotient.digits.size() - 1;
    for (size_t j = 0; 2 * j <= last_num; ++j) {
        std::swap(quotient.digits[j], quotient.digits[last_num - j]);
    }
    quotient.delete_nulls();
    *this = quotient;
    is_positive = (start_sign == div_number.is_positive);
    return *this;
}

BigInteger &BigInteger::operator%=(const BigInteger &div_number) {
    BigInteger copy = *this;
    copy /= div_number;
    *this = (*this - copy * div_number);
    return *this;
}

BigInteger operator+(const BigInteger& a, const BigInteger& b) {
    BigInteger copy = a;
    copy += b;
    return copy;
}
BigInteger operator-(const BigInteger& a, const BigInteger& b) {
    BigInteger copy = a;
    copy -= b;
    return copy;
}
BigInteger operator*(const BigInteger& a, const BigInteger& b) {
    BigInteger copy = a;
    copy *= b;
    return copy;
}
BigInteger operator/(const BigInteger& a, const BigInteger& b) {
    BigInteger copy = a;
    copy /= b;
    return copy;
}
BigInteger operator%(const BigInteger& a, const BigInteger& b) {
    BigInteger copy = a;
    copy %= b;
    return copy;
}

class Rational;

bool operator< (const Rational& a, const Rational& b);

class Rational {
private:
    BigInteger numerator = 0; ///числитель
    BigInteger denominator = 1;
    ///когда тормозится обычный алгоритм евклида
    static BigInteger gcd(const BigInteger a, const BigInteger b) {
        if (a == b || b == 0) {
            return  a;
        }
        if (a == 0) {
            return b;
        }
        if (a % 2 == 0 && b % 2 == 0) {
            return 2 * gcd(a/2, b/2);
        }
        if (a % 2 == 0) {
            return gcd(a/2, b);
        }
        if (b % 2 == 0) {
            return gcd(a, b/2);
        }
        if (a < b) {
            return gcd((b - a)/2, a); ///делим на 2 чтобы сразу пропустить след шаг
        }
        return gcd((a - b)/2, b);
    } ///как работает алгоритм евклида для отрицательных
    void reduce() { ///сокращает на gcd и делает так что - только в числителе может быть
        if (numerator.sign() != denominator.sign()) {
            numerator *= denominator.sign();
            denominator *= denominator.sign();
        } else {
            denominator *= denominator.sign();
            numerator *= numerator.sign();
        }
        BigInteger div = gcd(numerator * numerator.sign(), denominator);
        numerator /= div;
        denominator /= div;
    }
public:
    BigInteger getNumerator() const { ///если по ссылке верну то смогу ли я менять потом?
        return numerator;
    }
    BigInteger getDenominator() const {
        return denominator;
    }
    Rational() = default;
    Rational(const int a): numerator(a) {}
    Rational(const BigInteger& a): numerator(a) {} ///если подать инт то всё скастуется тк есть конструктор бигинта из инта
    Rational(const Rational& a) = default; ///если не прописать то не было бы копирования???

    Rational& operator+=(const Rational& a) {
        numerator *= a.denominator;
        numerator += a.numerator * denominator;
        denominator *= a.denominator;
        reduce();
        return *this;
    }
    Rational& operator-=(const Rational& a) {
        numerator *= a.denominator;
        numerator -= a.numerator * denominator;
        denominator *= a.denominator;
        reduce();
        return *this;
    }
    Rational& operator*=(const Rational& a) {
        numerator *= a.numerator;
        denominator *= a.denominator;
        reduce();
        return *this;
    }
    Rational& operator/=(const Rational& a) { ///что с делением на 0?
        numerator *= a.denominator;
        denominator *= a.numerator;
        reduce();
        return *this;
    }
    Rational operator-() const {
        Rational copy(*this);
        copy *= -1;
        return copy;
    }
    std::string toString() const { ///ИДЕЯ: использовать toString из бигинтов
        std::string ans_str = numerator.toString();
        if (denominator != 1) {
            ans_str += "/";
            ans_str += denominator.toString();
        }
        return ans_str;
    }
    std::string asDecimal(size_t precision) const {
        std::string ans_str;
        if (*this < 0) {
            ans_str += "-";
        }
        BigInteger first(numerator * numerator.sign());
        first /= denominator;
        ans_str += first.toString() + ".";
        BigInteger div = numerator * numerator.sign() % denominator;
        for (size_t i = 1; i <= precision; ++i) {
            ans_str += (div * 10 / denominator).toString();
            div = div * 10 % denominator;
        }
        return ans_str;
    }

    explicit operator double() const {
        return atof(asDecimal(50).c_str());
    }
};

bool operator==(const Rational& a, const Rational& b) { ///на данном этапе все дроби сокращены и - только вверху может быть
    if (a.getNumerator() == 0 && b.getNumerator() == 0) {
        return true;
    }
    return (a.getNumerator() == b.getNumerator() && a.getDenominator() == b.getDenominator());
}
bool operator!=(const Rational& a, const Rational& b) {
    return !(a == b);
}
bool operator<(const Rational& a, const Rational& b) {
    if (a.getNumerator().sign() != b.getNumerator().sign()) {
        return (b.getNumerator().sign() == 1);
    }
    return (a.getNumerator() * b.getDenominator() < b.getNumerator() * a.getDenominator());
}
bool operator>(const Rational& a, const Rational& b) {
    return b < a;
}
bool operator<=(const Rational& a, const Rational& b) {
    return (a < b || a == b);
}
bool operator>=(const Rational& a, const Rational& b) {
    return (a > b || a == b);
}

Rational operator+(const Rational& a, const Rational& b) {
    Rational copy(a);
    copy += b;
    return copy;
}
Rational operator-(const Rational& a, const Rational& b) {
    Rational copy(a);
    copy -= b;
    return copy;
}
Rational operator*(const Rational& a, const Rational& b) {
    Rational copy(a);
    copy *= b;
    return copy;
}
Rational operator/(const Rational& a, const Rational& b) {
    Rational copy(a);
    copy /= b;
    return copy;
}

std::ostream& operator<<(std::ostream& out, const Rational& a) {
    std::string temp_s = a.toString();
    out << temp_s;
    return out;
}

int main() {
    BigInteger b, k;
    b = 0, k = 1234567;
    std::ostringstream oss;
    oss << b << ' ' << k;
    if (oss.str() != "0 1234567") {
        std::cerr<<("Assignment from int, or stream output failed.\n");
    }

    BigInteger a = b;
    a = -a;
    std::string testString = a.toString() + " " + (-k).toString();
    if (testString != "0 -1234567") {
        std::cerr<<("Unary minus or toString method failed.\n");
    }

    a = 999, b = 1000;
    a = a += a;
    testString = a.toString();
    if (testString != "1998") {
        std::cerr<<("Operator = or += failed.\n");
    }
    ++a %= a /= a *= a -= b++;
    std::ostringstream oss2;
    oss2 << 5+a << ' ' << 1-b; // 5 -1000
    if (oss2.str() != "5 -1000") {
        std::cerr<<oss2.str();
    }

    std::ostringstream oss3;
    oss3 << (a = (bool(a) ? -1 : -2));
    if (oss3.str() != "-2") {
        std::cerr<<("BigIntegerests failed.\n");
    }

    std::istringstream iss("26 5");
    iss >> a >> b;
    std::ostringstream oss4;
    oss4 << b << ' ' << a << ' ';
    if (oss4.str() != "5 26 ") {
        std::cerr<<("Stream input or output failed.\n");
    }

    oss4 << a+b << ' ' << a-b << ' ' << a*b << ' ' << a/b << ' ' << a%b << '\n';
    oss4 << b+a << ' ' << b-a << ' ' << b*a << ' ' << b/a << ' ' << b%a;
    if (oss4.str() != "5 26 31 21 130 5 1\n31 -21 130 0 5") {
        std::cerr<<("Arithmetic operations failed.\n");
    }

    std::vector<BigInteger> v;
    for (size_t i = 0; i < 1000; ++i) {
        v.push_back(1000 - i);
    }
    std::sort(v.begin(), v.end());

    std::ostringstream oss5;
    oss5 << v[0] << ' ' << v[500] << ' ' << v[999] << ' ';

    oss5 << (a != b) << ' ' << (a < b) << ' ' << (a > b) << ' ';
    oss5 << (a <= b) << ' ' << (a >= b);
    if (oss5.str() != "1 501 1000 1 0 1 0 1") {
        std::cerr<<("Rationalelation operations failed.\n");
    }
    std::istringstream iss2("1000000000000000000000000000000000 -1000000");
    iss2 >> a >> b;
    std::ostringstream oss6;
    oss6 << b << a;
    if (oss6.str() != "-10000001000000000000000000000000000000000") {
        std::cerr<<("Stream input or output failed.\n");
    }

    std::istringstream iss3("453234523460009834520987234598234502345987029345436345634563 "
                            "234523452034623049872345234520983475325345234232578");
    BigInteger c, d;
    iss3 >> c >> d;

    std::istringstream iss4("-23534576554950000000000000009999990000999900000 "
                            "8888888888884444444444433333333333332222222222222111112222777777777");
    BigInteger e, f;
    iss4 >> e >> f;

    std::ostringstream oss7;

    oss7 << a+b << ' ' << c+d << ' ' << e+f;
    if (oss7.str() != "999999999999999999999999999000000 "
                      "453234523694533286555610284470579736866970504670781579867141 "
                      "8888888888884444444420898756778383332222222222212111122221777877777") {
        std::cerr<<("Operatori + failed.\n");
    }

    std::ostringstream oss8;
    oss8 << a-b << ' ' << c-d << ' ' << e-f;
    if (oss8.str() != "1000000000000000000000000001000000 "
                      "453234523225486382486364184725889267825003554020091111401985 "
                      "-8888888888884444444467967909888283332222222222232111102223777677777") {
        std::cerr<<("Operator - failed.\n");
    }

    std::ostringstream oss9;
    oss9 << a*b << ' ' << c*d << ' ' << e*f;
    if (oss9.str() != "-1000000000000000000000000000000000000000 "
                      "106294125023108851855435239407742287054686671354449187194200406809777590661604024572718537860109672117737393414 "
                      "-209196236043895401881977738593593744982694026094492829962212043149123345328234038901116544451103777729999222300000") {
        std::cerr<<("Operator * failed.\n");
    }

    std::ostringstream oss10;
    oss10 << a/b << ' ' << c/d << ' ' << e/f;
    if (oss10.str() != "-1000000000000000000000000000 1932576548 0") {
        std::cerr<<("Operator / failed.\n");
    }
    std::ostringstream oss11;
    oss11 << a%b << ' ' << c%d << ' ' << e%f;
    if (oss11.str() != "0 101894444317458440603421824036688159663989325253819 "
                       "-23534576554950000000000000009999990000999900000") {}

    Rational r;
    r = 5;
    r += 3;
    r *= 7;
    b = 15;
    (r /= 8) -= b;
    if (-r != 8)
        std::cerr<<("BigIntegerest 1 failed.\n");

    Rational s, t;
    s = Rational(85)/37, t = Rational(29)/BigInteger(-163);
    s += t; ///неправильный числитель
    t = 1;
    for (int i = 0; i < 15; ++i)
        t *= s;

    if ((1/t).toString() != "507972178875842800075597772950831264898404875587494819951"
                            "/39717526884730183825748150063721595142668632339785349901549568")
        std::cerr<<("BigIntegerest 2 failed.\n");
    s = 4*3*7*13*19*41*43*11; // 2^2×3×7×13×19×41×43×11
    t = -17*13*23*79;
    s *= s*s, t *= t*t;
    Rational q = s/t;
    if (q.toString() != "-29650611427828166204352/29472131485369")
        std::cerr<<("BigIntegerest 3 failed.\n");
    if (q/1000000000 >= 1)
        std::cerr<<("BigIntegerest 4 failed.\n");

    Rational x(0 / q);
    Rational y(0);
    if (x == y) {
        std::cout << "YES";
    }
    q *= t/s;
    if (q != 1 || q.toString() != "1")
        std::cerr<<("BigIntegerest 6 failed.\n");
    s = 4*3*7*13*19*41*43*11;
    t = s - 25; // t=402365939
    s = 1000000007;
    s *= 1000000009;
    s *= 2147483647;
    if ((s/t).asDecimal(10) != "5337140829307966068.3989202202")
        std::cerr<<("BigIntegerest 7 failed.\n");
    t = -t;
    if ((t/s).asDecimal(25) != "-0.0000000000000000001873662")
        std::cerr<<("BigIntegerest 8 failed.\n");
///0 * отрицательно это будет отрицательным или каким?
}