#include <iostream>
#include <vector>

using namespace std;

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

public:
    Polynomial(const vector<T>& v) {
        data = v;
        while (data.size() != 0 && data.back() == static_cast<T>(0)) {
            data.pop_back();
        }
    }

    Polynomial(const T& l = static_cast<T>(0)) {
        data = {l};
        if (data[0] == static_cast<T>(0)) {
            data.clear();
        }
    }

    template <typename Iterator>
    Polynomial(Iterator first, Iterator second) {
        while (first != second) {
            data.push_back(*first++);
        }
        while (data.size() != 0 && data.back() == static_cast<T>(0)) {
            data.pop_back();
        }
    }

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

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

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

    const T operator[] (size_t i) const {
        if (i >= data.size() || i < 0) {
            return static_cast<T>(0);
        }
        return data[i];
    }

    bool operator == (const Polynomial<T>& other) const {
        return data == other.data;
    }

    bool operator == (const T& l) const {
        Polynomial<T> p(l);
        return *this == p;
    }

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

    bool operator != (const T& l) const {
        return !(*this == l);
    }

    Polynomial<T> operator + (const Polynomial<T>& other) const {
        size_t M = data.size();
        size_t N = other.data.size();
        vector<T> temp(max(M, N));
        for (size_t i = 0; i != max(M, N); ++i) {
            temp[i] = (*this)[i] + other[i];
        }
        Polynomial<T> p(temp);
        return p;
    }

    Polynomial<T> operator + (const T& l) const {
        Polynomial<T> p(l);
        return *this + p;
    }

    Polynomial<T> operator - (const Polynomial<T>& other) const {
        size_t M = data.size();
        size_t N = other.data.size();
        vector<T> temp(max(M, N));
        for (size_t i = 0; i != max(M, N); ++i) {
            temp[i] = (*this)[i] - other[i];
        }
        Polynomial<T> p(temp);
        return p;
    }

    Polynomial<T> operator - (const T& l) const {
        Polynomial<T> p(l);
        return *this - p;
    }

    Polynomial<T>& operator += (const Polynomial<T>& other) {
        size_t M = data.size();
        size_t N = other.data.size();
        vector<T> temp(max(M, N));
        for (size_t i = 0; i != max(M, N); ++i) {
            temp[i] = (*this)[i] + other[i];
        }
        *this = Polynomial<T>(temp);
        return *this;
    }

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

    Polynomial<T>& operator -= (const Polynomial<T>& other) {
        size_t M = data.size();
        size_t N = other.data.size();
        vector<T> temp(max(M, N));
        for (size_t i = 0; i != max(M, N); ++i) {
            temp[i] = (*this)[i] - other[i];
        }
        *this = Polynomial<T>(temp);
        return *this;
    }

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

    Polynomial<T> operator * (const Polynomial<T>& other) const {
        size_t M = data.size();
        size_t N = other.data.size();
        vector<T> temp(M + N);
        for (size_t i = 0; i != M; ++i) {
            for (size_t j = 0; j != N; ++j) {
                temp[i + j] += (*this)[i] * other[j];
            }
        }
        Polynomial<T> p(temp);
        return p;
    }

    Polynomial<T> operator * (const T& l) const {
        size_t M = data.size();
        vector<T> temp(M);
        for (size_t i = 0; i != M; ++i) {
            temp[i] = (*this)[i] * l;
        }
        Polynomial<T> p(temp);
        return p;
    }

    Polynomial<T>& operator *= (const Polynomial<T>& other) {
        size_t M = data.size();
        size_t N = other.data.size();
        vector<T> temp(M + N);
        for (size_t i = 0; i != M; ++i) {
            for (size_t j = 0; j != N; ++j) {
                temp[i + j] += (*this)[i] * other[j];
            }
        }
        *this = Polynomial<T>(temp);
        return *this;
    }

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

    T operator () (const T& l) const {
        if (data.size() == 0) {
            return T(0);
        }
        int n = data.size() - 1;
        T b = data[n];
        --n;
        while (n >= 0) {
            b = data[n] + b * l;
            --n;
        }
        return b;
    }

    Polynomial<T> operator & (const Polynomial<T>& p) const {
        if (data.size() == 0) {
            return Polynomial<T>(T(0));
        }
        int n = data.size() - 1;
        Polynomial<T> b = data[n];
        --n;
        while (n >= 0) {
            b = data[n] + b * p;
            --n;
        }
        return b;
    }

    Polynomial<T> operator / (const Polynomial<T>& other) const {
        if (data.size() < other.data.size()) {
            return Polynomial<T>(T(0));
        }
        vector<T> temp = data;
        Polynomial<T> t(temp);
        vector<T> ans(data.size());
        vector<T> v(data.size());
        while (t.Degree() >= other.Degree()) {
            v[t.Degree() - other.Degree()] = t.data.back() / other.data.back();
            size_t i = t.Degree() - other.Degree();
            ans[i] = v[i];
            Polynomial<T> V(v);
            t -= V * other;
            v[i] = T(0);
        }
        Polynomial<T> A(ans);
        return A;
    }

    Polynomial<T> operator / (const T& l) const {
        vector<T> v = data;
        for (size_t i = 0; i != data.size(); ++i) {
            v[i] /= l;
        }
        Polynomial<T> ans(v);
        return ans;
    }

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

    Polynomial<T> operator , (const Polynomial<T>& other) const {
        Polynomial<T> tmp2 = other;
        Polynomial<T> tmp1 = *this;
        Polynomial<T> tmp;
        while (tmp2.Degree() != -1) {
            tmp = tmp1;
            tmp1 = tmp2;
            tmp2 = tmp % tmp1;
        }
        tmp1 = tmp1 / tmp1[tmp1.Degree()];
        return tmp1;
    }
};

template <typename T>
bool operator == (const T& l, const Polynomial<T>& p1) {
    return p1 == l;
}

template <typename T>
bool operator != (const T& l, const Polynomial<T>& p1) {
    return !(p1 == l);
}

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

template <typename T>
Polynomial<T> operator - (const T& l, const Polynomial<T>& p1) {
    Polynomial<T> p(l);
    return p - p1;
}

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

template <typename T>
ostream& operator << (ostream& out, const Polynomial<T>& p) {
    for (int i = p.Degree(); i != -1; --i) {
        if (p[i] > T(0) && i != p.Degree()) {
            out << '+';
        }
        if (p[i] == T(-1)) {
            out << '-';
            if (i == 0) {
                out << 1;
            }
        }
        if (p[i] == T(1) && i == 0) {
            out << 1;
        }
        if (p[i] != T(0) && p[i] != T(-1) && p[i] != T(1)) {
            out << p[i];
            if (i != 0) {
                out << '*';
            }
        }
        if (p[i] != T(0)) {
            if (i > 1) {
                out << 'x' << '^' << i;
            }
            if (i == 1) {
                out << 'x';
            }
        }
    }
    if (p.Degree() == -1) {
        out << 0;
    }
    return out;
}