program ridke_matice;
{  Nasobeni ridkych matic ( dynamicka alokace )
   Tuetschek 2005
}


type PMatice = ^TMatice;
     TMatice = record       {prvky matice}
               x,y:integer;
               h:integer;
               r,d:PMatice;
               end;
     MMatice = record       {hlavicka - dimenze, odkaz na matici}
               r,c:integer;
               M:PMatice;
               end;
     Znaky   = set of char; {pro nacitani ze vstupu}

const cislice   : znaky = ['0','1','2','3','4','5','6','7','8','9'];

Procedure New_Matrix (var a: MMatice);
{inicializace nove matice, a.M musi byt nil}
begin;
New (a.M);
a.r:=0;
a.c:=0;
a.M^.x:=-1;
a.M^.y:=-1;
a.M^.h:=-1;
a.M^.r:=nil;
a.M^.d:=nil;
end;

Procedure Set_Item (var M: PMatice; x,y,h: integer);
var q,r,c: PMatice;


begin;
r:=M;
c:=M;
while (c^.r<> nil) and (c^.r^.x <=x) do c:=c^.r;
while (r^.d<> nil) and (r^.d^.y <=y) do r:=r^.d;
{vyhledani v hlavicce}

if (c^.x<>x) then begin;
   New (q);
   q^.x:=x;
   q^.y:=-1;
   q^.r:=c^.r;
   q^.d:=nil;
   c^.r:=q;
   c:=q;
   end;{vytvoreni noveho sloupce}

if (r^.y<>y) then begin;
   New (q);
   q^.x:=-1;
   q^.y:=y;
   q^.d:=r^.d;
   q^.r:=nil;
   r^.d:=q;
   r:=q;
   end;{vytvoreni noveho radku}

while (c^.d<> nil) and (c^.d^.y <=y) do c:=c^.d;

if (c^.y = y) then
   begin;
   c^.h:=h;
   Exit;
   {prvek existuje - zmeni hodnotu}
   end  else

   begin;
   while (r^.r<> nil) and (r^.r^.x <=x) do r:=r^.r;
   New (q);
   q^.x:=x;
   q^.y:=y;
   q^.d:=c^.d;
   q^.r:=r^.r;
   c^.d:=q;
   r^.r:=q;
   q^.h:=h;
   end;{vytvoreni noveho prvku}

end;

Procedure Del_Matrix (var M: PMatice);
{smaze matici z pameti }
var r,c,q:PMatice;

begin;
r:=M;
c:=M;
while (r <> nil) do
  begin;
  c:=r^.r;{predpoklada nenulove radky}
  while (c <> nil) do
    begin;
    q:=c;
    c:=c^.r;
    dispose (q);
    end;
  q:=r;
  r:=r^.d;
  dispose (q);
  end;
end;

Procedure Write_Matrix (var M: PMatice);
{vypise nenulove prvky matice, nevypisuje dimenze}
var r,c:PMatice;

begin;
r:=M;
c:=M;
if (r = nil) then
   begin;
   Writeln('-1');
   Exit;
   {matice je nulova}
   end
else r:=r^.d;
while (r <> nil) do
  begin;
  c:=r^.r;{predpoklada nenulove radky}
  while (c <> nil) do
    begin;
    Writeln(c^.x,',',c^.y,',',c^.h); {oddeluje carkou}
    c:=c^.r;
    end;
  r:=r^.d;
  end;
end;{procedure}

Procedure Nasob (var a,b,c : MMatice);
{vynasobi A x B, vysledek zapise do C }
var ra,rb,ca,cb: PMatice;
    suma       : integer;

begin;
if (c.M<> nil) then Del_Matrix (c.M);
if a.c<>b.r then Exit; {nelze nasobit}
New_Matrix (c);
ra:=a.M;
ca:=a.M;
rb:=b.M;
cb:=b.M;
c.r:=a.r;
c.c:=b.c;
if (ra<>nil) then ra:=ra^.d;
while (ra<>nil) do
  begin;
  if (b.M<>nil) then cb:=b.M^.r;
  while (cb<>nil) do
     begin;
     ca:=ra^.r;
     rb:=cb^.d;
     suma:=0;
     while (ca<>nil) and (rb<>nil)
     do if (ca^.x > rb^.y) then rb:=rb^.d
     else if (ca^.x < rb^.y) then ca:=ca^.r
     else begin;
          suma:=suma + (ca^.h * rb^.h);
          rb:=rb^.d;
          ca:=ca^.r;
          end;
     if (suma<>0) then Set_Item ( c.M, cb^.x, ra^.y, suma );
     cb:=cb^.r;
     end;
  ra:=ra^.d;
end;
end;

Function Input ( var oddel :char ) : integer;
{nacte cislo, do oddel ulozi znak, ktery byl za nim}
var c: char;
    a: integer;
    z: boolean; {znamenko - minus=true }
begin;
c:=#0;
a:=0;
z:=false;
Read(c);
if c in cislice then a:=Ord(c) - 48
else if c='-' then z:=true
else c:=#0;
if (c<>#0) then begin;
   Read(c);
   while c in cislice do
         begin;
         a:=(10 * a) + (Ord(c) - 48);
         Read(c);
         end;
   end;
if z then a:= -1 * a;
input:= a;
oddel:= c;
if c=#13 then Read(c);
{predpoklada stisknuti enter - #13 #10}
end;


var a,b,c : MMatice;
    x,y,h : integer;
    err   : char;

begin;
{predpoklada aspon trochu smysluplne zadani
 - na vstupu musi byt matice, s rozmery na zacatku,
 s jednotl. polozkami na radcich. Oddeleni - carkou,
 mezerou, cimkoliv. Pokud na vstupu najde 0 (nebo zap. cislo)
 a za nim #13 #10, ukonci zadavani prvni matice,
 prechazi na druhou }

x:=input(err);
y:=input(err);
New_Matrix(a);
a.r:=y;
a.c:=x;
repeat
x:=input(err);
if ((err=#13) or (err=#10)) and (x<=0) then Break;
y:=input(err);
h:=input(err);
if ((h<>0) and (x>=0) and (y>=0) and (x<a.c) and (y<a.r))
   then set_item(a.M,x,y,h);
until false;
{nacteni prvni matice}

x:=input(err);
y:=input(err);
New_Matrix(b);
b.r:=y;
b.c:=x;
repeat
x:=input(err);
if ((err=#13) or (err=#10)) and (x<=0) then Break;
y:=input(err);
h:=input(err);
if ((h<>0) and (x>=0) and (y>=0) and (x<b.c) and (y<b.r))
   then set_item(b.M,x,y,h);
until false;
{nacteni druhe matice}

Nasob(a,b,c);
{vynasobeni}

if (a.c=b.r) then Writeln(b.c,',',a.r);
Write_Matrix(c.M);
{vypis}

Del_Matrix(b.M);
Del_Matrix(c.M);
Del_Matrix(a.M);
{dispose}
end.