#include <cstddef>
#include <map>
#include <vector>
#include <iostream>

template<typename T>
T power(T x, int pw) {
    T res(T(1));
    while (pw > 0) {
        if (pw % 2 == 1) {
            res *= x;
        }
        pw /= 2;
        x *= x;
    }
    return res;
}

template <typename T>
class Polynomial {
private:
    std::map<int, T> coef;

    void Compress() {
        std::vector<int> toErase;
        for (const auto& i : coef) {
            if (i.second == T(0)) {
                toErase.push_back(i.first);
            }
        }
        for (const auto& i : toErase) {
            coef.erase(i);
        }
    }

public:
    Polynomial(const std::vector<T>& arr) {
        for (size_t i = 0; i < arr.size(); ++i) {
            coef[i] = arr[i];
        }
        Compress();
    }

    Polynomial(const std::map<int, T>& arr) : coef(arr) {
        Compress();
    }

    Polynomial(T el = T(0)) {
        coef[0] = el;
        Compress();
    }

    template<typename K>
    Polynomial(K beginIt, const K& endIt) {
        int i = 0;
        while (beginIt != endIt) {
            coef[i++] = *(beginIt++);
        }
        Compress();
    }

    int Degree() const {
        if (coef.size() == 0) {
            return -1;
        } else {
            return coef.rbegin()->first;
        }
    }

    T operator[](const size_t& n) const {
        if (coef.count(n)) {
            return coef.at(n);
        } else {
            return T(0);
        }
    }

    typename std::map<int, T>::const_iterator begin() const {
        return coef.begin();
    }

    typename std::map<int, T>::const_iterator end() const {
        return coef.end();
    }

    Polynomial& operator += (const std::map<int, T>& other) {
        for (const auto& i : other) {
            coef[i.first] += i.second;
        }
        Compress();
        return *this;
    }

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

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

    Polynomial operator + (const std::map<int, T>& other) const {
        return Polynomial(*this) += other;
    }

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

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

    Polynomial& operator -= (const std::map<int, T>& other) {
        for (const auto& i : other) {
            coef[i.first] -= i.second;
        }
        Compress();
        return *this;
    }

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

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

    Polynomial operator - (const std::map<int, T>& other) const {
        return Polynomial(*this) -= other;
    }

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

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

    bool operator == (const std::map<int, T>& other) const {
        return coef == other;
    }

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

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

    bool operator != (const std::map<int, T>& other) const {
        return !(*this == other);
    }

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

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

    Polynomial& operator *= (const std::map<int, T>& other) {
        if (Degree() == -1 || other.size() == 0) {
            return *this = Polynomial();
        }
        std::map<int, T> res;
        for (const auto& i : *this) {
            for (const auto& j : other) {
                res[i.first + j.first] += i.second * j.second;
            }
        }
        return *this = Polynomial(res);
    }

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

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

    Polynomial operator * (const std::map<int, T>& other) const {
        return Polynomial(*this) *= other;
    }

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

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

    T operator () (const T& x) const {
        T res = T(0);
        for (const auto& i : *this) {
            res += power<T>(x, i.first) * i.second;
        }
        return res;
    }

    Polynomial operator & (const Polynomial& other) const {
        Polynomial res(T(0));
        for (const auto& i : *this) {
            res += power(other, i.first) * i.second;
        }
        return res;
    }

    Polynomial operator / (const Polynomial& other) const {
        Polynomial res(T(0)), residue(*this);
        while (residue.Degree() >= other.Degree()) {
            Polynomial temp = power(Polynomial(std::vector<T>{T(0), T(1)}),
            residue.Degree() - other.Degree())
            * (residue[residue.Degree()] / other[other.Degree()]);
            res += temp;
            residue -= temp * other;
        }
        return res;
    }

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

    Polynomial operator , (const Polynomial& other) const {
        Polynomial a(*this), b(other);
        while ((a * b) != Polynomial(T(0))) {
            Polynomial temp = a % b;
            a = b;
            b = temp;
        }
        if (a == Polynomial(T(0))) {
            return b / Polynomial(b[b.Degree()]);
        } else {
            return a / Polynomial(a[a.Degree()]);
        }
    }
};

template<typename T>
std::ostream& operator << (std::ostream& out, const Polynomial<T>& p) {
    if (p.Degree() == -1) {
        out << T(0);
        return out;
    }
    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];
            continue;
        }
        if (p[i] == T(-1)) {
            out << '-';
        } else if (p[i] != T(1)) {
            out << p[i] << '*';
        }
        if (i > 1) {
            out << "x^" << i;
        } else {
            out << 'x';
        }
    }
    return out;
}

template<typename T>
Polynomial<T> power(Polynomial<T> f, int pw) {
    Polynomial<T> res(T(1));
    while (pw > 0) {
        if (pw % 2 == 1) {
            res *= f;
        }
        f *= f;
        pw /= 2;
    }
    return res;
}