Cerința

Se consideră o matrice pătratică A=(ai,j)de ordin n, elementele sale fiind cifre în baza 10. Pentru fiecare element ai,j al matricei definim drumul de la elementul a1,1 la elementul ai,j ca fiind format din elementele: a1,1, a2,1, …, ai,1, ai,2, ai,3, …, ai,j. Pentru fiecare element ai,j al matricei, se cere să se calculeze suma produselor oricăror două elemente situate pe drumul de la elementul a1,1 la elementul ai,j.

Date de intrare

Fișierul de intrare matprod.in conține pe prima linie numărul n, iar pe următoarele n linii câte n cifre separate prin spaţiu, reprezentând elementele matricei A.

Date de ieșire

Fișierul de ieșire matprod.out va conține pe primele n linii câte n numere naturale separate prin spaţiu, reprezentând suma cerută pentru fiecare element al matricei.

Restricții și precizări

• 2 ≤ n ≤ 1000
• elementele matricei A sunt cifre

Exemplu:

matprod.in

3
1 2 3 
4 5 0
9 3 7

matprod.out

0 2 11
4 29 29
49 91 210

Explicație

De exemplu, pentru elementul a3,2, drumul este format din 1, 4, 9, 3, iar suma este 1•4+1•9+1•3+4•9+4•3+9•3=91.