#include <iostream>
#include <stdio.h>
using namespace std;

#define MAX_N 100

struct s_triplet{
	int linie, coloana, valoare;
};

struct s_matrice_rara{
	int num_linii, num_coloane;
	int num_elemente;
	s_triplet elemente[MAX_N];
};

int mai_mic_lex(s_triplet t1, s_triplet t2);
void inserare(s_matrice_rara &m, s_triplet x);
int determina_element(s_matrice_rara &m, int linie, int coloana);
void citire(s_matrice_rara &m);
void suma(s_matrice_rara &a, s_matrice_rara &b, s_matrice_rara &c);
void produs(s_matrice_rara &a, s_matrice_rara &b, s_matrice_rara &p);
void afiseaza(s_matrice_rara &m);

int main(void)
{
	s_matrice_rara a, b, c, p;

	citire(a);
	citire(b);

	afiseaza(a);
	afiseaza(b);

	suma(a, b, c);
	afiseaza(c);

	produs(a, b, p);
	afiseaza(p);

	return 0;
}

int mai_mic_lex(s_triplet t1, s_triplet t2)
{
	if (t1.linie < t2.linie)
		return 1;
	if (t1.linie == t2.linie && t1.coloana < t2.coloana)
		return 1;
	return 0;
}

void inserare(s_matrice_rara &m, s_triplet x)
{
	if (m.num_elemente == 0)
		m.elemente[0] = x;
	else{
		int i = m.num_elemente;
		while (i > 0 && mai_mic_lex(x, m.elemente[i - 1])){
			m.elemente[i] = m.elemente[i - 1];

			i--;
		}
		m.elemente[i] = x;
	}
	m.num_elemente++;
}

int determina_element(s_matrice_rara &m, int linie, int coloana)
{
	for (int k = 0; k < m.num_elemente; k++)
		if (m.elemente[k].linie == linie && m.elemente[k].coloana == coloana)
			return m.elemente[k].valoare;
	return 0;
}

void citire(s_matrice_rara &m)
{

	cout << "introduceti numarul de linii = ";
	cin >> m.num_linii;
	cout << "introduceti numarul de coloane = ";
	cin >> m.num_coloane;

	m.num_elemente = 0;

	s_triplet t;
	cin >> t.linie >> t.coloana >> t.valoare;

	while (!(t.linie == -1 && t.coloana == -1 && t.valoare == -1)){
		if (determina_element(m, t.linie, t.coloana) == 0)       // daca tripletul nu a fost inserat  deja
			inserare(m, t);
		cin >> t.linie >> t.coloana >> t.valoare;
	}
}

void suma(s_matrice_rara &a, s_matrice_rara &b, s_matrice_rara &c)
{
	c.num_coloane = a.num_coloane;
	c.num_linii = a.num_linii;
	c.num_elemente = 0;

	for (int i = 1; i <= c.num_linii; i++)
		for (int j = 1; j <= c.num_coloane; j++)
		{
		     int s = determina_element(a, i, j) + determina_element(b, i, j);
   	             if (s != 0)
   	             {
					s_triplet t;

					t.linie = i;
					t.coloana = j;
					t.valoare = s;
					inserare(c, t);
				}
	    }
}

void produs(s_matrice_rara &a, s_matrice_rara &b, s_matrice_rara &p)
{
	p.num_coloane = a.num_coloane;
	p.num_linii = a.num_linii;
	p.num_elemente = 0;


    for(int i = 1;i <= p.num_linii ; i++)
        for(int j = 1;j <= p.num_coloane; j++)
    {
        s_triplet t;
        t.linie = i;
        t.coloana = j;
        t.valoare = 0;

        for(int k = 1; k <= p.num_coloane; k++)
				t.valoare+= determina_element(a, i, k) *  determina_element(b, k, j);

		inserare(p, t);

    }

}

void afiseaza(s_matrice_rara &m)
{
	for (int i = 1; i <= m.num_linii; i++){
		for (int j = 1; j <= m.num_coloane; j++)
			cout << determina_element(m, i, j) << " ";
		cout << '\n';;
	}
	cout <<'\n';
}

/*
 2 2
 1 1 6
 1 2 7
 2 1 8
 2 2 9
 -1 -1 -1
 2 2
 1 1 1
 1 2 2
 2 1 3
 2 2 4
 -1 -1 -1

 *
 */