simetric

O matrice pătratică $A$ care are $P$ linii şi $P$ coloane este simetrică dacă şi numai dacă pentru orice indici $i$ şi $j$ între $1$ şi $P$ avem că $A_{i, j} = A_{j, i}$. Astfel, matricea din figura 1 este simetrică, iar cea din figura 2 nu este, deoarece există cel puţin o pereche de indici (de exemplu $i = 2$ şi $j = 3$), pentru care $A_{i, j}$ este diferit de $A_{j, i}$.

Pentru o matrice dată cu $M$ linii şi $N$ coloane, definim submatricea de vârfuri $(l_1, c_1)$ şi $(l_2, c_2)$, cu $1 \leq l_1 \leq l_2 \leq M$ şi $1 \leq c_1 \leq c_2 \leq N$, ca fiind tabloul format din toate elementele de coordonate $i$ şi $j$ astfel încât $l_1 \leq i \leq l_2$ şi $c_1 \leq j \leq c_2$.

Cerință

Se dă o matrice cu $M$ linii şi $N$ coloane în care toate elementele sunt numere naturale. Fie $L$ latura maximă a unei submatrici simetrice din această matrice. Pentru fiecare dimensiune $i$ între $1$ si $L$ să se determine câte submatrici simetrice şi cu latura $i$ ale matricei date există.

Date de intrare

Prima linie a fişierului simetric.in conţine numerele $M$ şi $N$, separate de exact un spaţiu, reprezentând numărul de linii, şi respectiv de coloane, ale matricei care se citeşte. Fiecare din următoarele $M$ linii conţine câte $N$ numere naturale, despărţite de exact un spaţiu, reprezentând elementele matricei.

Date de ieșire

Fişierul de ieşire simetric.out conţine exact $L$ linii, unde $L$ este latura maximă a unei submatrici simetrice din matricea considerată. Linia $i$ conţine numărul de submatrici simetrice de latură $i$.

Restricții și precizări

• $2 \leq M, N \leq 400$
• Elementele matricei sunt numere naturale cuprinse între $1$ şi $30 \ 000$.

Exemplu

simetric.in

4 5
5 1 3 6 9
1 6 2 8 9
3 2 7 5 1
9 8 5 3 8

simetric.out

20
3
2

Explicație

Există $20$ de submatrici simetrice de latură $1$ (fiecare celulă este considerată submatrice), $3$ submatrici simetrice de latură $2$ şi $2$ de latură $3$. Submatricile simetrice de latură $3$ sunt:

$\begin{bmatrix} 5 & 1 & 3 \\ 1 & 6 & 2 \\ 3 & 2 & 7 \\ \end{bmatrix}$ respectiv $\begin{bmatrix} 6 & 2 & 8 \\ 2 & 7 & 5 \\ 8 & 5 & 3 \\ \end{bmatrix}$