#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#include <cassert>

using namespace std;

template<typename T>
class Matrix;

template<typename T>
class MatrixIterator {
private:
    const Matrix<T>& matrix;
    size_t row;
    size_t column;

public:
    MatrixIterator(const Matrix<T>& m, size_t i, size_t j) : matrix(m), row(i), column(j) {
    }

    bool operator == (MatrixIterator other) const {
        return row == other.row && column == other.column;
    }

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

    const T& operator * () const {
        return matrix[row][column];
    }

    MatrixIterator& operator++ () {
        ++column;
        if (column == matrix[0].size()) {
            ++row;
            column = 0;
        }
        return *this;
    }

    MatrixIterator operator++ (int) {
        auto tmp = *this;
        ++*this;
        return tmp;
    }
};

template<typename T>
class NoMatrixIterator {
private:
    Matrix<T>& matrix;
    size_t row;
    size_t column;

public:
    NoMatrixIterator(Matrix<T>& m, size_t i, size_t j) : matrix(m), row(i), column(j) {
    }

    bool operator == (NoMatrixIterator other) const {
        return row == other.row && column == other.column;
    }

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

    T& operator * () const {
        return matrix[row][column];
    }

    NoMatrixIterator& operator++ () {
        ++column;
        if (column == matrix[0].size()) {
            ++row;
            column = 0;
        }
        return *this;
    }

    NoMatrixIterator operator++ (int) {
        auto tmp = *this;
        ++*this;
        return tmp;
    }
};

template<typename T>
class Matrix {
private:
    size_t N;
    size_t M;
    vector<vector<T> > data;

public:
    Matrix(const vector<vector<T> >& a) {
        data = a;
        N = a.size();
        M = a[0].size();
    }

    NoMatrixIterator<T> begin() {
        return{ *this, 0, 0 };
    }

    const MatrixIterator<T> begin() const {
        return{ *this, 0, 0 };
    }

    NoMatrixIterator<T> end() {
        return{ *this, data.size(), 0 };
    }

    const MatrixIterator<T> end() const {
        return{ *this, data.size(), 0 };
    }

    const vector<T>& operator[] (size_t i) const {
        return data[i];
    }

    vector<T>& operator[] (size_t i) {
        return data[i];
    }

    pair<size_t, size_t> size() const {
        return make_pair(N, M);
    }

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

    Matrix<T> operator + (const Matrix<T>& a) const {
        Matrix<T> ans(data);
        ans += a;
        return ans;
    }

    template<typename B>
    Matrix<T>& operator *= (const B& a) {
        for (size_t i = 0; i < N; ++i) {
            for (size_t j = 0; j < M; ++j) {
                data[i][j] *= a;
            }
        }
        return *this;
    }

    template<typename B>
    Matrix<T> operator * (const B& a) const {
        Matrix<T> ans(data);
        ans *= a;
        return ans;
    }

    Matrix<T>& transpose() {
        vector<vector<T> > a;
        a.resize(M);
        for (size_t i = 0; i < M; ++i) {
            a[i].resize(N);
        }
        for (size_t i = 0; i < M; ++i) {
            for (size_t j = 0; j < N; ++j) {
                a[i][j] = data[j][i];
            }
        }
        Matrix<T> ans(a);
        data = ans.data;
        M = ans.M;
        N = ans.N;
        return *this;
    }

    Matrix<T> transposed() const {
        vector<vector<T> > a;
        a.resize(M);
        for (size_t i = 0; i < M; ++i) {
            a[i].resize(N);
        }
        for (size_t i = 0; i < M; ++i) {
            for (size_t j = 0; j < N; ++j) {
                a[i][j] = data[j][i];
            }
        }
        Matrix<T> ans(a);
        return a;
    }

    Matrix<T>& operator *= (const Matrix<T> a) {
        assert(M == a.N);
        vector<vector<T> > q;
        q.resize(N);
        for (size_t i = 0; i < N; ++i) {
            q[i].resize(a.M);
        }
        for (size_t i = 0; i < N; ++i) {
            for (size_t j = 0; j < a.M; ++j) {
                for (size_t k = 0; k < M; ++k) {
                    q[i][j] += data[i][k] * a.data[k][j];
                }
            }
        }
        data = q;
        M = a.M;
        return *this;
    }

    Matrix<T> operator * (const Matrix<T>& a) const {
        assert(M == a.N);
        vector<vector<T> > q;
        q.resize(N);
        for (size_t i = 0; i < N; ++i) {
            q[i].resize(a.M);
        }
        for (size_t i = 0; i < N; ++i) {
            for (size_t j = 0; j < a.M; ++j) {
                for (size_t k = 0; k < M; ++k) {
                    q[i][j] += data[i][k] * a.data[k][j];
                }
            }
        }
        Matrix<T> ans(q);
        return ans;
    }
};

template<typename T>
ostream& operator<<(ostream& out, const Matrix<T>& m) {
    for (size_t i = 0; i < m.size().first; ++i) {
        for (size_t j = 0; j < m.size().second; ++j) {
            if (j == m.size().second - 1) {
                out << m[i][j];
            } else {
                out << m[i][j] << "\t";
            }
        }
        if (i == m.size().first - 1) {
            continue;
        }
        out << "\n";
    }
    return out;
}