#include <iostream>
#include <vector>


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

    void normalize() {
        if (data.empty()) {
            size = 0;
        } else {
            size_t pos = data.size() - 1;
            while (data[pos] == static_cast<T>(0) && pos != 0) {
                data.pop_back();
                --pos;
            }
            if (data.size() == 1 && data[0] == static_cast<T>(0)) {
                data.pop_back();
            }
            size = data.size();
        }
    }

public:
    Polynomial<T>(const std::vector<T> &a):data(a) {
        this->normalize();
    }

    template <typename Iter>
    Polynomial<T>(Iter first, Iter last) {
        while (first != last) {
            data.push_back(*first++);
        }
        this->normalize();
    }

    Polynomial<T>(const T &num = T()) {
        data.push_back(num);
        this->normalize();
    }

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

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

    size_t Range() const {
        return  data.size();
    }

    bool operator == (const Polynomial<T> &other) const {
        if (this->Degree() != other.Degree()) {
            return false;
        }
        for (size_t i = 0; i != this->Range(); ++i) {
            if (data[i] != other[i]) {}
            return false;
        }
        return true;
    }

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

    Polynomial<T>& operator += (const Polynomial<T> &other) {
        std::vector<T> ans = {};
        ans.resize(std::max(this->Range(), other.Range()));
        for (size_t i = 0; i != this->Range(); ++i) {
            ans[i] = data[i];
        }
        for (size_t i = 0; i != other.Range(); ++i) {
            ans[i] += other[i];
        }
        data = ans;
        normalize();
        return *this;
    }

    Polynomial<T>& operator -= (const Polynomial<T> &other) {
        std::vector<T> ans = {};
        ans.resize(std::max(this->Range(), other.Range()));
        for (size_t i = 0; i != this->Range(); ++i) {
            ans[i] = data[i];
        }
        for (size_t i = 0; i != other.Range(); ++i) {
            ans[i] -= other[i];
        }
        data = ans;
        normalize();
        return *this;
    }

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

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

template <typename T>
Polynomial<T> operator +(const Polynomial<T> &first, const Polynomial<T> &second) {
    auto copy(first);
    return copy += second;
}

template <typename T>
Polynomial<T> operator +(const Polynomial<T> &poly, const T &num) {
    auto  copy(poly);
    return copy += Polynomial<T>(num);
}

template <typename T>
Polynomial<T> operator +(const T &num, const Polynomial<T> &poly) {
    auto  copy(poly);
    return copy += Polynomial<T>(num);
}

template <typename T>
Polynomial<T> operator -(const Polynomial<T> &first, const Polynomial<T> &second) {
    auto copy(first);
    return copy -= second;
}

template <typename T>
Polynomial<T> operator -(const Polynomial<T> &poly, const T &num) {
    auto  copy(poly);
    return copy -= Polynomial<T>(num);
}

template <typename T>
Polynomial<T> operator -(const T &num, const Polynomial<T> &poly) {
    auto  copy(poly);
    return copy -= Polynomial<T>(num);
}

int main() {
    Polynomial<int> a({1, 2, 3}), b({4, 5, 6});
    std::cout << a.Degree() << ' ' << b.Degree() << a[2] << ' ' << b[2] << (a + b)[2];
    Polynomial<int> c(a.begin(), a.end());
}