//Developed by Nikita Mikaev
#ifndef MY_MATRIX
#define MY_MATRIX
#include <iostream>
#include <cassert>
using namespace std;


template <class T>
class Matrix{
    private:
        T **data;
        int rows,cols;
        void null_init();
    public:
        Matrix(int rows_=0,int cols_=0);
        Matrix(const Matrix<T> &from);
        ~Matrix();
        int Rows() const{return rows;};
        int Cols() const{return cols;};
        T Get(int row,int col) const;
        void Set(int row,int col, T value);
        Matrix<T> operator+(const Matrix<T> &arg);
        Matrix<T>& operator=(const Matrix<T> &arg);
        Matrix<T> operator*(const Matrix<T> &arg);
        //template<class T,typename T2> Matrix<T> operator*(const Matrix<T> &arg, T2 value);
        template<class A, typename T2> friend Matrix<T> operator*(T2 value, const Matrix<T> &arg);
        template<class A> friend ostream& operator<<(ostream &out,const Matrix<T> &arg);
        Matrix<T> Transp();
};

template <class T>
Matrix<T> Matrix<T>::Transp(){
    Matrix<T> temp(Cols(),Rows());
    for(int j=0;j<Cols();j++){
        for(int i=0;i<Rows();i++)
            temp.Set(j,i,Get(i,j));
    }
    return temp;
}

template <class T>
Matrix<T>::Matrix(int rows_,int cols_){
    assert(rows_>=0 and cols_>=0);
    rows=rows_;
    cols=cols_;
    data=new T*[rows];
    for(int i=0;i<rows;i++)
        data[i]=new T[cols];
    null_init();
}

template <class T>
Matrix<T>::Matrix(const Matrix &from){
    rows=from.Rows();
    cols=from.Cols();
    data=new T*[rows];
    for(int i=0;i<rows;i++)
        data[i]=new T[cols];
    for(int i=0;i<rows;i++){
        for(int j=0;j<cols;j++)
            Set(i,j,from.Get(i,j));
    }
}

template <class T>
Matrix<T>::~Matrix(){
    for(int i=0;i<cols;i++)
        delete[] data[i];
    delete[] data;
}

template <class T>
T Matrix<T>::Get(int row,int col) const{
    assert(row>=0 and row<rows and col>=0 and col<cols);
    return data[row][col];
}

template <class T>
void Matrix<T>::Set(int row, int col, T value){
    assert(row>=0 and row<rows and col>=0 and col<cols);
    data[row][col]=value;
}

template <class T>
Matrix<T> Matrix<T>::operator+(const Matrix<T> &arg){
    assert(rows==arg.Rows() and cols==arg.Cols());
    Matrix<T> temp(rows,cols);
    for(int i=0;i<rows;i++){
        for(int j=0;j<cols;j++)
            temp.Set(i,j,Get(i,j)+arg.Get(i,j));
    }
    return temp;
}

template <class T>
Matrix<T>& Matrix<T>::operator=(const Matrix<T> &arg){
    rows=arg.Rows();
    cols=arg.Cols();
    for(int i=0;i<rows;i++){
        for(int j=0;j<cols;j++)
            data[i][j]=arg.Get(i,j);
    }
    return *this;
}

template <class T>
Matrix<T> Matrix<T>::operator*(const Matrix<T> &arg){
    assert(Cols()==arg.Rows());
    int minimal=min(min(Rows(),Cols()),min(arg.Rows(),arg.Cols()));
    Matrix<T> temp(Rows(),arg.Cols());
    for(int i=0;i<temp.Rows();i++){
        for(int j=0;j<temp.Cols();j++){
            for(int s=0;s<Cols();s++){
                int sum=temp.Get(i,j)+Get(i,s)*arg.Get(s,j);
                temp.Set(i,j,sum);
            }
        }
    }
    return temp;
}

template<class T> ostream& operator<<(ostream &out,const Matrix<T> &arg){
    for(int i=0;i<arg.Rows();i++){
        for(int j=0;j<arg.Cols();j++)
            out<<arg.Get(i,j)<<" ";
        cout << endl;
    }
    return out;
}

template<class T>
void Matrix<T>::null_init(){

    for(int i=0;i<Rows();i++){
        for(int j=0;j<Cols();j++)
            Set(i,j,0);
    }
}

/*template<class T, typename T2> Matrix<T> operator*(const Matrix<T> &arg, T2 value){
    Matrix<T> temp(arg);
    for(int i=0;i<temp.Rows();i++){
        for(int j=0;j<temp.Cols();j++)
            temp.Set(i,j,temp.Get(i,j)*value);
    }
    return temp;
}*/

template<class A, typename T> Matrix<A> operator*(T value, const Matrix<A> &arg){
    Matrix<A> temp(arg);
    for(int i=0;i<temp.Rows();i++){
        for(int j=0;j<temp.Cols();j++)
            temp.Set(i,j,temp.Get(i,j)*value);
    }
    return temp;
}
#endif