#include <iostream>
#include <vector>

template<typename T>
class Matrix {
    std::vector<std::vector<T>> a;

public:
    Matrix(const std::vector<std::vector<T>> &b) : a(b) {
    }

    Matrix(int N, int M) {
        a.resize(N);
        for (int i = 0; i < N; ++i) a[i].resize(M);
    }

    std::pair<size_t, size_t> size() const {
        std::pair<size_t, size_t> ans = {a.size(), 0};
        if (a.size())
            ans.second = a[0].size();
        return ans;
    }

    std::vector<T> &operator[](int i) {
        return a[i];
    }

    const std::vector<T> &operator[](int i) const {
        return a[i];
    }

    Matrix<T> &operator+=(const Matrix<T> &other) {
        for (size_t i = 0; i < a.size(); ++i) {
            for (size_t j = 0; j < a[0].size(); ++j) {
                a[i][j] += other[i][j];
            }
        }
        return *this;
    }

    Matrix<T> operator+(const Matrix<T> &other) const {
        Matrix<T> ans(*this);
        ans += other;
        return ans;
    }

    template<typename TT>
    Matrix<T> &operator*=(const TT &x) {
        for (size_t i = 0; i < a.size(); ++i) {
            for (size_t j = 0; j < a[0].size(); ++j) {
                a[i][j] *= x;
            }
        }
        return *this;
    }

    Matrix<T> &operator*=(const Matrix<T> &other) {
//        if (a[0].size() != other.size().first) std::cerr << "kek\n";
        std::vector<std::vector<T>> ans(a.size(), std::vector<T>(other.size().second));
        for (size_t i = 0; i < a.size(); ++i) {
            for (size_t k = 0; k < a[0].size(); ++k) {
                for (size_t j = 0; j < other.size().second; ++j) {
                    ans[i][j] += a[i][k] * other[k][j];
                }
            }
        }
        swap(a, ans);
        return *this;
    }

    Matrix<T> operator*(const Matrix<T> &other) const {
        auto ans(*this);
        ans *= other;
        return ans;
    }

    template<typename TT>
    Matrix<T> operator*(const TT &x) const {
        Matrix<T> ans(*this);
        ans *= x;
        return ans;
    }

    Matrix<T> &transpose() {
        std::vector<std::vector<T>> ans(a[0].size(), std::vector<T>(a.size()));
        for (size_t i = 0; i < a.size(); ++i) {
            for (size_t j = 0; j < a[0].size(); ++j) {
                ans[j][i] = a[i][j];
            }
        }
        std::swap(a, ans);
        return *this;
    }

    Matrix<T> transposed() const {
        Matrix<T> ans(*this);
        ans.transpose();
        return ans;
    }

    template<typename U>
    std::vector<U> solve(const std::vector<U> &B) {
        const U EPS = 1e-9;
        std::vector<std::vector<U>> A(a.size());
        for (size_t i = 0; i < a.size(); i++) {
            A[i].resize(a[i].size());
            for (size_t j = 0; j < a[i].size(); j++) {
                A[i][j] = a[i][j];
            }
        }
        int n = A.size();
        for (int i = 0; i < n; i++) {
            A[i].push_back(B[i]);
        }
        int m = static_cast<int>(A[0].size()) - 1;
        std::vector<int> where(m, -1);
        std::vector<std::pair<int, int>> sw;
        for (int col = 0, row = 0; col < m && row < n; ++col) {
            int sel = row;
            for (int i = row; i < n; ++i)
                if (abs(A[i][col]) > abs(A[sel][col]))
                    sel = i;
            if (abs(A[sel][col]) < EPS)
                continue;
            for (int i = col; i <= m; ++i)
                std::swap(A[sel][i], A[row][i]);
            sw.push_back({sel, row});
            where[col] = row;
            for (int i = 0; i < n; ++i)
                if (i != row) {
                    U c = A[i][col] / A[row][col];
                    for (int j = col; j <= m; ++j)
                        A[i][j] -= A[row][j] * c;
                }
            ++row;
        }
        std::vector<U> ans;
        ans.assign(m, 0);
        for (int i = 0; i < m; ++i)
            if (where[i] != -1) {
                U x = A[where[i]][m] / A[where[i]][i];
                ans[i] = U(x);
            }
        /*for (auto it : sw) {
            std::swap(ans[it.first], ans[it.second]);
        }*/
        return ans;
    }

    class iterator {
    public:
        typedef iterator self_type;
        typedef T value_type;
        typedef T &reference;
        typedef T *pointer;
        typedef std::forward_iterator_tag iterator_category;
        typedef int difference_type;

        iterator(size_t x, size_t y, size_t n, size_t m, std::vector<std::vector<T>> *tmp)
                : x(x), y(y), n(n), m(m), a(tmp) {}

        self_type &operator++() {
            ++y;
            if (y == m) {
                x++;
                y = 0;
            }
            return *this;
        }

        reference operator*() { return (*a)[x][y]; }

        bool operator==(const self_type &rhs) { return x == rhs.x && y == rhs.y && a == rhs.a; }

        bool operator!=(const self_type &rhs) { return !((*this) == rhs); }

    private:
        size_t x, y, n, m;
        std::vector<std::vector<T>> *a;
    };

    class const_iterator {
    public:
        typedef const_iterator self_type;
        typedef T value_type;
        typedef const T &reference;
        typedef T *pointer;
        typedef std::forward_iterator_tag iterator_category;
        typedef int difference_type;

        const_iterator(int x, int y, size_t n, size_t m, const std::vector<std::vector<T>> *tmp)
                : x(x), y(y), n(n), m(m), a(tmp) {}

        self_type &operator++() {
            ++y;
            if (y == m) {
                x++;
                y = 0;
            }
            return *this;
        }

        const reference operator*() { return (*a)[x][y]; }

        bool operator==(const self_type &rhs) { return x == rhs.x && y == rhs.y && a == rhs.a; }

        bool operator!=(const self_type &rhs) { return !((*this) == rhs); }

    private:
        size_t x, y, n, m;
        const std::vector<std::vector<T>> *a;
    };

    iterator begin() {
        return iterator(0, 0, static_cast<int>(a.size()), static_cast<int>(a[0].size()), &a);
    }

    iterator end() {
        return iterator(a.size(), 0, static_cast<int>(a.size()), static_cast<int>(a[0].size()), &a);
    }

    const_iterator begin() const {
        return const_iterator(0, 0, static_cast<int>(a.size()), static_cast<int>(a[0].size()), &a);
    }

    const_iterator end() const {
        return const_iterator(a.size(), 0,
                              static_cast<int>(a.size()), static_cast<int>(a[0].size()), &a);
    }
};

template<typename T>
std::ostream &operator<<(std::ostream &out, const Matrix<T> &m) {
    auto mSize = m.size();
    for (size_t i = 0; i < mSize.first; ++i) {
        if (i != 0)
            out << '\n';
        for (size_t j = 0; j < mSize.second; ++j) {
            if (j)
                out << '\t';
            out << m[i][j];
        }
    }
    return out;
}