#include <iostream>
const int maxsize = 32;

class Matrix {
	public:
		Matrix(){}
		Matrix(int);
		friend Matrix operator* (const Matrix&, const Matrix& );
		friend Matrix operator+ (const Matrix&, const Matrix& );
		friend Matrix operator- (const Matrix&, const Matrix& );
		friend ostream& operator<< (ostream& , const Matrix&);

	private:
		int size;
		int m[maxsize][maxsize];
		void partition(Matrix& , Matrix& , Matrix& , Matrix& ) const;
		void merge(const Matrix& ,const Matrix& ,const Matrix& ,const Matrix& );
};

Matrix::Matrix(int n)
{
	int i, j;
	size = n;
	for(i = 0; i < size; i++) {
		for(j = 0; j < size; j++) {
			m[i][j] = 0;
		}
		m[i][i] = 1;
	}
}

ostream& operator<< (ostream& out, const Matrix &a)
{
	int i, j;
	for(i = 0; i < a.size; i++) {
		for(j = 0; j < a.size; j++) {
			cout << "[" << a.m[i][j] << "]"; 
		}
		cout << endl;
	}
	return out;
}

void Matrix::partition(Matrix &a11, Matrix &a12, Matrix &a21, Matrix &a22) const
{
	int i, j;
	a11.size = a12.size = a21.size = a22.size = size / 2;

	for(i = 0; i < size / 2; i++) {
		for(j = 0; j < size / 2; j++) {
			a11.m[i][j] = m[i][j];
			a12.m[i][j] = m[i][j + size / 2];
			a21.m[i][j] = m[i + size / 2][j];
			a22.m[i][j] = m[i + size / 2][j + size / 2];
		}
	}

}

void Matrix::merge(const Matrix &a11,const Matrix &a12,const Matrix &a21,const Matrix &a22)
{
	int i, j;
	size = a11.size * 2;

	for(i = 0; i < size / 2; i++) {
		for(j = 0; j < size / 2; j++) {
			m[i][j] = a11.m[i][j];
			m[i][j + size / 2] = a12.m[i][j];
			m[i + size / 2][j] = a21.m[i][j];
			m[i + size / 2][j + size / 2] = a22.m[i][j];
		}
	}
}

Matrix operator+ (const Matrix &a, const Matrix &b)
{
	int i, j;
	Matrix tmp = a;
	for(i = 0; i < a.size; i++) {
		for(j = 0; j < a.size; j++) {
			tmp.m[i][j] += b.m[i][j];
		}
	}
	return tmp;
}

Matrix operator- (const Matrix &a, const Matrix &b)
{
	int i, j;
	Matrix tmp = a;
	for(i = 0; i < a.size; i++) {
		for(j = 0; j < a.size; j++) {
			tmp.m[i][j] -= b.m[i][j];
		}
	}
	return tmp;
}

Matrix operator* (const Matrix &a,const Matrix &b)
{
	Matrix tmp, a11, a12, a21, a22, b11, b12, b21, b22, m1, m2, m3, m4, m5, m6, m7;

	tmp.size = a.size;

	if(a.size == 1) {
		tmp.m[0][0] = a.m[0][0] * b.m[0][0];
		return tmp;
	}

	a.partition(a11, a12, a21, a22);
	b.partition(b11, b12, b21, b22);

	m1 = (a11 + a22) * (b11 + b22);
	m2 = (a21 + a22) * b11;
	m3 = a11 * (b12 - b22);
	m4 = a22 * (b21 - b11);
	m5 = (a11 + a12) * b22;
	m6 = (a21 - a11) * (b11 + b12);
	m7 = (a12 - a22) * (b21 + b22);

	tmp.merge( m1 + m4 - m5 + m7, m3 + m5, m2 + m4, m1 + m3 - m2 + m6);

	return tmp;
}

main()
{
	Matrix a(8), b(8);

	cout << a * b;
}