identice

Mihai a construit o matrice pătratică $A$ de dimensiune $N$ cu valori în mulțimea ${0,1}$. El preferă acele matrice care au toate elementele identice și de aceea a calculat pentru matricea $A$, numărul $K$ de submatrice care au toate elementele identice. Acum, Mihai vrea să transforme matricea $A$ într-o matrice cu toate elementele identice. Pentru aceasta, el a selectat un număr natural nenul $D$, și definește operația ZET care constă în alegerea unei submatrice pătratice de dimensiunea $D$ din matricea precedentă în care schimbă toate elementele $0$ în $1$ și invers. El vrea să aplice operația ZET inițial pentru matricea $A$, apoi repetă operația pentru matricea obținută la momentul anterior, de un număr minim de ori, notat $R$, până când matricea obținută are toate elementele identice, sau dacă nu este posibil, $R$ va avea valoarea $-1$.

Cerință

Mihai vă roagă să calculați valorile $K$ și $R$. Pentru a preciza tipul cerinței, Mihai folosește un cod $T$ care dacă are valoarea $1$, atunci solicită calcularea valorii $K$, iar dacă $T$ are valoarea $2$, atunci solicită calcularea valorii $R$.

Date de intrare

Pe prima linie a fișierului identice.in se vor afla numerele naturale $T, N$ și $D$, cu semnificația de mai sus, separate prin câte un spațiu. Pe următoarele $N$ linii se vor afla câte $N$ valori de $0$ și $1$, elementele liniilor matricei $A$, fără spații între ele.

Date de ieșire

Pe prima linie a fișierului identice.out se va afla un număr natural, respectiv valoarea $K$ pentru $T = 1$ sau valoarea $R$ pentru $T = 2$.

Restricții și precizări

• $1 < D < N \leq 1 \ 000;$
• Pentru calcularea valorii $K$, submatricele pot fi pătratice sau dreptunghiulare, cu diferite dimensiuni (inclusiv $1$), cu elementele identice$;$
• Se acordă $40$ din punctaj pentru determinarea corectă a lui $K$ iar pentru determinarea corectă a lui $R$ se acordă $60$ din punctajul total$.$

Exemplul 1

identice.in

1 4 2
0011
0011
1100
1100

identice.out

36

Explicație

$T = 1$, deci se calculează $K = 36$. Sunt $18$ submatrice cu toate elementele $0$ și $18$ cu toate elementele $1$.

Exemplul 2

identice.in

2 4 2
0011
0011
1100
1100

identice.out

2

Explicație

$T = 2$, deci se calculează $R = 2$, deoarece sunt necesare $2$ aplicări ale operației ZET.