#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>

template <typename T>
class Polynomial {
private:
    std::vector<T> coefficients = {};

    void clear_zeroes() {
        for (int i = static_cast<int>(coefficients.size()) - 1; i > -1; --i) {
            if (coefficients[i] == static_cast<T>(0)) {
                coefficients.pop_back();
            } else {
                break;
            }
        }
    }

    void resize(int s) {
        coefficients.resize(s);
    }

public:
    Polynomial() = default;

    Polynomial(const T& t) {
        coefficients = {};
        coefficients.push_back(t);
        this->clear_zeroes();
    }

    Polynomial(const std::vector<T>& v) {
        coefficients = {};
        coefficients = std::move(v);
        this->clear_zeroes();
    }

    template <typename InIter>
    Polynomial(InIter first, InIter last) {
        coefficients = {};
        while (first != last) {
            coefficients.push_back(*first++);
        }
        this->clear_zeroes();
    }

    void clear_z() {
        clear_zeroes();
    }

    const std::vector<T>& GetCoeff() const {
        return coefficients;
    }

    int Degree() const {
        return static_cast<int>(coefficients.size()) - 1;
    }

    T& at(int i) {
        if (i > Degree()) {
            coefficients.resize(i + 1);
        }
        return coefficients[i];
    }

    T operator[] (int i) const {
        if (i > this->Degree()) {
            return static_cast<T>(0);
        }
        return coefficients[i];
    }

    bool operator == (const Polynomial& p) const {
        return coefficients == p.GetCoeff();
    }

    bool operator != (const Polynomial& p) const {
        return coefficients != p.GetCoeff();
    }

    Polynomial& operator += (const Polynomial& p) {
        if (coefficients.size() < p.GetCoeff().size()) {
            coefficients.resize(p.GetCoeff().size());
        }
        for (size_t i = 0; i < p.GetCoeff().size(); ++i) {
            coefficients[i] += p.GetCoeff()[i];
        }
        this->clear_zeroes();
        return *this;
    }

    Polynomial& operator -= (const Polynomial& p) {
        if (coefficients.size() < p.GetCoeff().size()) {
            coefficients.resize(p.GetCoeff().size());
        }
        for (size_t i = 0; i < p.GetCoeff().size(); ++i) {
            coefficients[i] -= p.GetCoeff()[i];
        }
        this->clear_zeroes();
        return *this;
    }

    Polynomial& minus(const Polynomial& p) {
        if (coefficients.size() < p.GetCoeff().size()) {
            coefficients.resize(p.GetCoeff().size());
        }
        for (size_t i = 0; i < p.GetCoeff().size(); ++i) {
            coefficients[i] -= p.GetCoeff()[i];
        }
        return *this;
    }

    Polynomial& operator *= (const Polynomial& p) {
        if (p.Degree() == -1) {
            coefficients.clear();
        } else if (this->Degree() != -1) {
            std::vector<T> new_coef(p.Degree() + this->Degree() + 1);
            for (int i = 0; i <= p.Degree(); ++i) {
                for (int j = 0; j <= this->Degree(); ++j) {
                    new_coef[i + j] += p.GetCoeff()[i] * coefficients[j];
                }
            }
            coefficients = std::move(new_coef);
            this->clear_zeroes();
        }
        return *this;
    }

    Polynomial operator + () const {
        return *this;
    }

    Polynomial operator - () const {
        Polynomial p(*this);
        for (int i = 0; i < p.GetCoeff().size(); ++i) {
            p[i] *= static_cast<T>(-1);
        }
        p.clear_zeroes();
        return p;
    }

    T operator ()(const T& t) const {
        T value = static_cast<T>(0);
        T curr = t;
        T beg = t;
        if (this->Degree() == -1) {
            return value;
        }
        value += coefficients[0];
        for (size_t i = 1; i < coefficients.size(); ++i) {
            value += curr * coefficients[i];
            curr *= beg;
        }
        return value;
    }

    typename std::vector<T>::const_iterator begin() const {
        return coefficients.begin();
    }

    typename std::vector<T>::const_iterator end() const {
        return coefficients.end();
    }

    Polynomial& to_canonic() {
        if (Degree() != -1) {
            T coef = coefficients[coefficients.size() - 1];
            for (int i = 0; i <= Degree(); ++i) {
                coefficients[i] /= coef;
            }
        }
        return *this;
    }

    Polynomial operator /= (const Polynomial& p) {
        Polynomial rest;
        while (rest.Degree() >= p.Degree()) {
            Polynomial result;
            result.at(rest.Degree() - p.Degree()) = rest[rest.Degree()] / p[p.Degree()];
            rest += result * p;
        }
        rest.clear_z();
        return rest;
    }

    ~Polynomial() {
        coefficients.clear();
    }
};

template <typename T>
Polynomial<T> operator + (const Polynomial<T>& p1, const Polynomial<T>& p2) {
    Polynomial<T> result = p1;
    return result += p2;
}

template <typename T>
Polynomial<T> operator - (const Polynomial<T>& p1, const Polynomial<T>& p2) {
    Polynomial<T> result = p1;
    return result -= p2;
}

template <typename T>
Polynomial<T> minus2(const Polynomial<T>& p1, const Polynomial<T>& p2) {
    Polynomial<T> result = p1;
    return result.minus(p2);
}

template <typename T>
Polynomial<T> operator * (const Polynomial<T>& p1, const Polynomial<T>& p2) {
    Polynomial<T> result = p1;
    return result *= p2;
}

template <typename T>
Polynomial<T> operator & (const Polynomial<T>& p1, const Polynomial<T>& p2) {
    Polynomial<T> preres;
    if (p1.Degree() != -1) {
        preres += p1[0];
        for (int i = 1; i <= p1.Degree(); ++i) {
            Polynomial<T> pow = p2;
            for (int j = 0; j < i - 1; ++j) {
                pow *= Polynomial<T>(p2);
            }
            preres += (Polynomial<T>(pow) * Polynomial<T>(p1[i]));
        }
    }
    return preres;
}

template<typename T>
Polynomial<T> operator / (Polynomial<T> p1, const Polynomial<T>& p2) {
    Polynomial<T> result = p1;
    return result /= p2;
}

template<typename T>
Polynomial<T> operator % (Polynomial<T> p1, const Polynomial<T>& p2) {
    Polynomial<T> rest = p1;
    while (rest.Degree() >= p2.Degree()) {
        Polynomial<T> result;
        result.at(rest.Degree() - p2.Degree()) =
            rest[rest.Degree()] / p2[p2.Degree()];
        rest -= result * p2;
    }
    rest.clear_z();
    return rest;
}

template <typename T>
Polynomial<T> operator , (const Polynomial<T>& p1, const Polynomial<T>& p2) {
    if (p2.Degree() == -1) {
        Polynomial<T> r = p1;
        r.to_canonic();
        return r;
    } else {
        return (p2, p1 % p2);
    }
}

template <typename T>
std::ostream& operator << (std::ostream& out, const Polynomial<T>& p) {
    for (int i = p.Degree(); i > 1; --i) {
        T coef = p.GetCoeff()[i];
        if (coef < static_cast<T>(0)) {
            if (coef == static_cast<T>(-1)) {
                out << "-x^" << i;
            } else {
                out << coef << "*x^" << i;
            }
        } else if (coef > static_cast<T>(0)) {
            if (p.Degree() != i) {
                out << "+";
            }
            if (coef == static_cast<T>(1)) {
                out << "x^" << i;
            } else {
                out << coef << "*x^" << i;
            }
        }
    }
    if (p.GetCoeff().size() >= 2) {
        T coef = p.GetCoeff()[1];
        if (coef < static_cast<T>(0)) {
            if (coef == static_cast<T>(-1)) {
                out << "-x";
            } else {
                out << coef << "*x";
            }
        } else if (coef > static_cast<T>(0)) {
            if (p.Degree() != 1) {
                out << "+";
            }
            if (coef == static_cast<T>(1)) {
                out << "x";
            } else {
                out << coef << "*x";
            }
        }
    }
    if (p.GetCoeff().size() >= 1) {
        T coef = p.GetCoeff()[0];
        if (coef > static_cast<T>(0)) {
            if (p.Degree() != 0) {
                out << "+";
            }
            out << coef;
        } else if (coef < static_cast<T>(0)) {
            out << coef;
        }
    }
    if (p.GetCoeff().size() == 0) {
        out << 0;
    }
    return out;
}

int main() {
    std::size_t nCoefficientsA;
    std::cout << "Number of <double> coefficients in the first vector: " << std::endl;
    std::cin >> nCoefficientsA;

    std::vector<double> coefficientsA;
    std::cout << "List of coefficients: " << std::endl;
    while (coefficientsA.size() < nCoefficientsA) {
        double coefficient;
        std::cin >> coefficient;
        coefficientsA.push_back(coefficient);
    }

    std::size_t nCoefficientsB;
    std::cout << "Number of <double> coefficients in the second vector: " << std::endl;
    std::cin >> nCoefficientsB;

    std::vector<double> coefficientsB;
    std::cout << "List of coefficients: " << std::endl;
    while (coefficientsB.size() < nCoefficientsB) {
        double coefficient;
        std::cin >> coefficient;
        coefficientsB.push_back(coefficient);
    }
    std::reverse(coefficientsA.begin(), coefficientsA.end());
    std::reverse(coefficientsB.begin(), coefficientsB.end());

    Polynomial<double> A(coefficientsA);
    Polynomial<double> B(coefficientsB);
    Polynomial<double> C(0);

    std::cout << "First vector: " << A << std::endl;
    std::cout << "Second vector: " << B << std::endl;
    std::cout << "Third vector: " << C << std::endl;

    if (A == B) {
        std::cout << "Equal" << std::endl;
    } else if (A != B) {
        std::cout << "Not Equal" << std::endl;
    }


    std::cout << "+  " << A + B << std::endl;

    std::cout << "-  " << A - B << std::endl;
    std::cout << "/ : " << (A / B) << std::endl;
    std::cout << "% : " << (A % B) << std::endl;
    std::cout << "WTF\n";
    std::cout << ", : " << (A , B) << std::endl;
    std::cout << A(-1) << '\n';

    std::cout << "List of the coefficients before variable degrees from 0 to 19: " << std::endl;
    for (int i = 0; i < 20; ++i) {
        std::cout << A[i] << " ";
    }
    std::cout << std::endl;
    auto i = A.begin();
    while (i != A.end()) {
        std::cout << *i++ << " ";
    }
    std::cout << '\n';
    std::cout << A.Degree();
    std::cout << '\n';
    std::cout << *A.begin();
}