#include <iostream>
#include <vector>
#include <string>
#include <functional>
#include <algorithm>

template <typename T>
class Monomial {
public:
    Monomial(const T& x) : coef(x), deegs(26) {}

    Monomial(const T& coef_tmp, const std::vector<int>& deegs_tmp) : coef(coef_tmp), deegs(deegs_tmp) {}

    auto begin() const {
        return deegs.begin();
    }

    auto end() const {
        return deegs.end();
    }

    auto rbegin() const {
        return deegs.rbegin();
    }

    auto rend() const {
        return deegs.rend();
    }

    T get_coef() const {
        return coef;
    }

    int operator[](size_t i) const {
        return deegs[i];

    }

    int& operator[](size_t i) {
        return deegs[i];

    }

    bool is_equal(const Monomial<T>& other) const {
        for (size_t i = 0; i < 26; ++i) {
            if (deegs[i] != other[i]) {
                return 0;
            }
        }
        return 1;
    }

    bool is_div(const Monomial<T>& other) const {
        for (size_t i = 0; i < 26; ++i) {
            if (deegs[i] < other[i]) {
                return false;
            }
        }
        return true;
    }

    Monomial<T>& operator *=(const T& x) {
        coef *= x;
        return *this;
    }

    Monomial<T> operator *(const T& x) const {
        Monomial<T> tmp_m = *this;
        return tmp_m *= x;
    }

    Monomial<T>& operator *=(const Monomial<T>& other) {
        coef *= other.get_coef();
        for (size_t i = 0; i < 26; ++i) {
            deegs[i] += other[i];
        }
        return *this;
    }

    Monomial<T> operator * (const Monomial<T>& other) const {
        Monomial<T> tmp_m = *this;
        return tmp_m *= other;
    }

    Monomial<T>& operator +=(const Monomial<T>& other) {
        // check for equal
        coef += other.get_coef();
        return *this;
    }

    Monomial<T> operator + (const Monomial<T>& other) const {
        Monomial<T> tmp_m;
        return tmp_m += other;
    }

    Monomial<T> operator/(const Monomial<T>& other) const {
        std::vector<int> tmp_deegs(26);
        for (size_t i = 0; i < 26; ++i) {
            tmp_deegs[i] = deegs[i] - other[i];
        }
        return { coef / other.get_coef(), tmp_deegs };
    }

    bool operator==(const Monomial<T>& other) const {
        return is_equal(other);
    }

    bool operator!=(const Monomial<T>& other) const {
        return !(is_equal(other));
    }

private:
    T coef;
    std::vector<int> deegs;
};

template <typename T>
class MonomialOrder {
public:
    MonomialOrder() {}

    MonomialOrder(const std::vector<std::function<bool(const Monomial<T>&, const Monomial<T>&)>>& tmp_mon_ord) {
        orders = tmp_mon_ord;
    }

    void add_order(const std::function<bool(const Monomial<T>&, const Monomial<T>&)>& func) {
        orders.push_back(func);
    }

    std::function<bool(const Monomial<T>&, const Monomial<T>&)> operator[](size_t i) const {
        return orders[i];
    }

    std::function<bool(const Monomial<T>&, const Monomial<T>&)>& operator[](size_t i) {
        return orders[i];
    }

    bool compair_less(const Monomial<T>& mon1, const Monomial<T>& mon2) const {
        for (auto func : orders) {
            if (func(mon1, mon2) != func(mon2, mon1)) {
                return func(mon1, mon2);
            }
        }
        return 0;
    }

    bool compair_less_or_eq(const Monomial<T>& mon1, const Monomial<T>& mon2) const {
        for (auto func : orders) {
            if (func(mon1, mon2) != func(mon2, mon1)) {
                return func(mon1, mon2);
            }
        }
        return 1;
    }

private:
    std::vector<std::function<bool(const Monomial<T>&, const Monomial<T>&)>> orders;
};

template <typename T>
bool lexicograph(const Monomial<T>& mon1, const Monomial<T>& mon2) {
    for (size_t i = 0; i < 26; ++i) {
        if (mon1[i] != mon2[i]) {
            return mon1[i] < mon2[i];
        }
    }
    return 0;
}

template <typename T>
class Polynomial {
public:
    Polynomial() {}

    Polynomial(const Monomial<T>& other_mon) {
        monoms.push_back(other_mon);
    }

    auto begin() const {
        return monoms.begin();
    }

    auto end() const {
        return monoms.end();
    }

    auto rbegin() const {
        return monoms.rbegin();
    }

    auto rend() const {
        return monoms.rend();
    }

    std::vector<Monomial<T>>& get_monoms() {
        return monoms;
    }

    size_t size() const {
        return monoms.size();
    }

    void dell_0() {
        for (size_t i = 0; i < size();) {
            if (monoms[i].get_coef() == 0) {
                monoms.erase(monoms.begin() + i);
            } else {
                ++i;
            }
        }
    }

    void dell_same_monoms_or_add(const Monomial<T>& other) {
        for (auto& monom : monoms) {
            if (monom.is_equal(other)) {
                monom += other;
                return;
            }
        }
        monoms.push_back(other);
    }

    Polynomial<T>& operator +=(const Monomial<T>& other) {
        bool diff = true;
        for (size_t i = 0; i < monoms.size(); ++i) {
            if (monoms[i].is_equal(other)) {
                monoms[i] += other.get_coef();
                diff = false;
            }
        }
        if (diff) {
            monoms.push_back(other);
        }
        dell_0();
        return *this;
    }

    Polynomial<T> operator + (const Monomial<T>& other) const {
        Polynomial<T> tmp_p = *this;
        return tmp_p += other;
    }

    Monomial<T> operator[](size_t i) const {
        return monoms[i];
    }

    Monomial<T>& operator[](size_t i) {
        return monoms[i];
    }

    Polynomial<T>& operator += (const Polynomial<T>& other) {
        for (const auto& mon_from_other : other.monoms) {
            *this += mon_from_other;
        }
        dell_0();
        return *this;
    }

    Polynomial<T> operator + (const Polynomial<T>& other) const {
        Polynomial<T> tmp_pol = *this;
        return tmp_pol += other;
    }

    Polynomial<T>& operator *= (const T& x) {
        for (auto& mon : monoms) {
            mon *= x;
        }
        dell_0();
        return *this;
    }

    Polynomial<T> operator *(const T& x) const {
        Polynomial<T> tmp_p = *this;
        return tmp_p *= x;
    }

    Polynomial<T>& operator *= (const Polynomial<T>& other) {
        Polynomial<T> tmp_p = *this;
        monoms.clear();
        for (const auto& mon_from_this : tmp_p.monoms) {
            for (const auto& mon_from_other : other.monoms) {
                *this += mon_from_this * mon_from_other;
            }
        }
        dell_0();
        return *this;
    }

    Polynomial<T> operator *(const Polynomial<T>& other) const {
        Polynomial<T> tmp_p = *this;
        return tmp_p *= other;
    }


    Polynomial<T>& operator -= (const Polynomial<T>& other) {
        *this *= -1;
        *this += other;
        *this *= -1;
        dell_0();
        return *this;
    }

    Polynomial<T> operator - (const Polynomial<T>& other) const {
        Polynomial<T> tmp_p = *this;
        return tmp_p -= other;
    }

    Polynomial<T> sort_pol(const MonomialOrder<T>& ord) {
        std::sort
        (
            monoms.begin()
            , monoms.end()
            , [&ord](Monomial<T> const& mon1, Monomial<T> const& mon2)
            {
                return ord.compair_less(mon1, mon2);
            }
        );
        return *this;
    }

    size_t size() {
        return monoms.size();
    }

private:
    std::vector<Monomial<T>> monoms;
};

template <typename T>
class PolynomialOrder {
public:
    PolynomialOrder() {}

    MonomialOrder<T>& get_mon_order() {
        return mon_order;
    }

    PolynomialOrder(const std::vector<std::function<bool(const Monomial<T>&, const Monomial<T>&)>>& tmp_mon_ord) {
        mon_order = tmp_mon_ord;
    }

    bool compair_less(Polynomial<T>& pol1, Polynomial<T>& pol2) {
        pol1.sort_pol(mon_order);
        pol2.sort_pol(mon_order);

        auto it1 = pol1.rbegin();
        auto it2 = pol2.rbegin();
        while (it1 != pol1.rend() && it2 != pol2.rend()) {
            if (*it1 != *it2) {
                return mon_order.compair_less(*it1, *it2);
            }
            ++it1;
            ++it2;
        }
        return pol1.size() < pol2.size();
    }

private:
    MonomialOrder<T> mon_order;
};

template <typename T>
class PolynomialSet {
public:
    PolynomialSet() {}

    PolynomialSet(const Polynomial<T>& pol) {
        pols.push_back(pol);
    }

    auto begin() {
        return pols.begin();
    }

    auto end() {
        return pols.end();
    }

    auto begin() const {
        return pols.begin();
    }

    auto end() const {
        return pols.end();
    }

    size_t size() {
        return pols.size();
    }

    Polynomial<T> operator[](size_t i) const {
        return pols[i];
    }

    Polynomial<T>& operator[](size_t i) {
        return pols[i];
    }

    void operator+=(const Polynomial<T>& pol) {
        pols.push_back(pol);
    }

private:
    std::vector<Polynomial<T>> pols;
};

template <typename T>
class Algorithm {
public:
    Algorithm(const MonomialOrder<T>& order) : ord(order) {}

    Polynomial<T> reduction(Polynomial<T> g, PolynomialSet<T> syst_f) const {
        g.sort_pol(ord);
        for (auto& pol : syst_f) {
            pol.sort_pol(ord);
        }

        for (size_t i = 0; i < g.size(); ++i) {
            Monomial<T> mon_from_g = g[i];
            bool can_red = true;
            while (can_red) {
                can_red = false;
                for (const auto& pol_from_s : syst_f) {
                    //
                    Monomial<T> mon_L = L(pol_from_s);
                    //
                    if (mon_from_g.is_div(mon_L)) {
                        //
                        Monomial<T> tmp_c = mon_from_g / mon_L;
                        Polynomial<T> tmp_p = pol_from_s * tmp_c; // shit is here
                        //
                        g -= tmp_p;
                        g.sort_pol(ord);
                        if (i >= g.size()) {
                            can_red = false;
                        } else {
                            mon_from_g = g[i];
                            can_red = true;
                        }
                        break;
                    }
                }
            }
        }
        return g.sort_pol(ord);
    }

    PolynomialSet<T> Buchberger(const PolynomialSet<T>& other_syst) const {
        PolynomialSet<T> ans_syst = other_syst;
        for (size_t i = 0; i < ans_syst.size(); ++i) {
            (ans_syst[i]).sort_pol(ord);
        }
        for (size_t i = 0; i < ans_syst.size(); ++i) {
            for (int j = i - 1; j >= 0; --j) {
                Polynomial<T> red_s_pol = reduction(S(ans_syst[i], ans_syst[j]), ans_syst);
                if (red_s_pol.size() != 0) { // need fixed this to check empty polynomial
                    ans_syst += red_s_pol;
                }
            }
        }
        return ans_syst;
    }

private:
    Monomial<T> L(const Polynomial<T>& p) const {
        return p[p.size() - 1];
    }

    std::pair<std::vector<int>, std::vector<int>> deegs_common_division(
        const Monomial<T>& m_1,
        const Monomial<T>& m_2) const {

        std::vector<int> tmp_deegs_1(26), tmp_deegs_2(26);
        for (size_t i = 0; i < 26; ++i) {
            tmp_deegs_1[i] = std::max(m_1[i], m_2[i]) - m_1[i];
            tmp_deegs_2[i] = std::max(m_1[i], m_2[i]) - m_2[i];
        }
        return { tmp_deegs_1, tmp_deegs_2 };
    }

    Polynomial<T> S(const Polynomial<T>& f_1, const Polynomial<T>& f_2) const {
        std::pair<std::vector<int>, std::vector<int>> tmp_deegs = deegs_common_division(L(f_1), L(f_2));
        Monomial<T> m_1(L(f_2).get_coef(), tmp_deegs.first);
        Monomial<T> m_2(L(f_1).get_coef(), tmp_deegs.second);
        return (f_1 * m_1 - f_2 * m_2).sort_pol(ord);
    }

    MonomialOrder<T> ord;
};