#include <algorithm>
#include <functional>
#include <iostream>
#include <map>

using namespace std;

template<typename T>
class Polynomial {
    private:
    vector<T> a;

    void clean() {
        while (!a.empty() && a.back() == T(0)) a.pop_back();
    }

    public:
    Polynomial(const vector<T>& other): a(other) { clean(); }

    Polynomial(T c = T()): a(1, c) { clean(); }

    template<typename It>
    Polynomial(It first, It last): a(first, last) { clean(); }

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

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

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

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

    int Degree() const {
        return a.size() - 1;
    }

    bool operator==(const Polynomial& other) const {
        return
            Degree() != other.Degree()
            ? false
            : equal(begin(), end(), other.begin(), other.end());
    }

    bool operator!=(const Polynomial& other) const {
        return !(*this == other);
    }

    const T operator[](int i) const {
        if (i > Degree()) return T(0);
        return a[i];
    }

    Polynomial& operator+=(const Polynomial& other) {
        if (Degree() < other.Degree()) a.resize(other.Degree() + 1, T(0));
        size_t min_sz = min(Degree(), other.Degree()) + 1;
        transform(begin(), begin() + min_sz,
                  other.begin(),
                  begin(),
                  plus<T>());
        clean();
        return *this;
    }

    Polynomial operator+(const Polynomial& other) const {
        Polynomial tmp(*this);
        tmp += other;
        return tmp;
    }

    Polynomial& operator-=(const Polynomial& other) {
        if (Degree() < other.Degree()) a.resize(other.Degree() + 1, T(0));
        size_t min_sz = min(Degree(), other.Degree()) + 1;
        transform(begin(), begin() + min_sz,
                  other.begin(),
                  begin(),
                  minus<T>());
        clean();
        return *this;
    }

    Polynomial operator-(const Polynomial& other) const {
        Polynomial tmp(*this);
        tmp -= other;
        return tmp;
    }

    Polynomial& operator*=(const Polynomial& other) {
        if (Degree() == -1 || other.Degree() == -1) {
            a.clear();
            return *this;
        }
        vector<T> result(Degree() + other.Degree() + 1, T(0));
        for (int i = 0; i <= Degree(); ++i) {
            for (int j = 0; j <= other.Degree(); ++j) {
                result[i + j] += (*this)[i] * other[j];
            }
        }
        a = move(result);
        clean();
        return *this;
    }

    Polynomial operator*(const Polynomial& other) const {
        Polynomial tmp(*this);
        tmp *= other;
        return tmp;
    }

    T operator()(const T& x) const {
        T result = T(0), power = T(1);
        for (int i = 0; i <= Degree(); ++i) {
            result += power * a[i];
            power *= x;
        }
        return result;
    }

    Polynomial operator&(const Polynomial& other) const {
        Polynomial result(T(0)), power(T(1));
        for (int i = 0; i <= Degree(); ++i) {
            result += power * (*this)[i];
            power *= other;
        }
        return result;
    }

    Polynomial operator/(const Polynomial& other) const {
        Polynomial q(T(0)), r(*this);
        while (r.Degree() != -1 && r.Degree() >= other.Degree()) {
            vector<T> tmp(r.Degree() - other.Degree() + 1, T(0));
            tmp.back() = r[r.Degree()] / other[other.Degree()];
            Polynomial t(tmp);
            q += t;
            r -= t * other;
        }
        return q;
    }

    Polynomial operator%(const Polynomial& other) const {
        Polynomial q(T(0)), r(*this);
        while (r.Degree() != -1 && r.Degree() >= other.Degree()) {
            vector<T> tmp(r.Degree() - other.Degree() + 1, T(0));
            tmp.back() = r[r.Degree()] / other[other.Degree()];
            Polynomial t(tmp);
            q += t;
            r -= t * other;
        }
        return r;
    }

    Polynomial operator,(const Polynomial& other) const {
        if (other == Polynomial(T(0))) {
            Polynomial result(*this);
            result = result / Polynomial(result[result.Degree()]);
            return result;
        } else {
            Polynomial r = (*this) % other;
            return (other, r);
        }
    }
};

template<typename T>
ostream& operator<<(ostream& out, const Polynomial<T>& p) {
    if (p.Degree() == -1) {
        out << T(0);
    } else {
        for (int i = p.Degree(); i >= 0; --i) {
            if (p[i] == T(0)) continue;

            if (i != p.Degree() && p[i] > T(0)) {
                out << '+';
            }
            if (i == 0) {
                out << p[i];
            } else {
                if (p[i] != T(1) && p[i] != T(-1)) out << p[i] << '*';
                if (p[i] == T(-1)) out << '-';
                out << 'x';
                if (i != 1) out << '^' << i;
            }
        }
    }
    return out;
}