== include(page="template/taskheader" task_id="pp") ==
Se da o matrice $A$ cu $M$ linii si $N$ coloane. Fiecare celula a matricii contine o litera mica a alfabetului englez $('a'-'z')$. Un *subpatrat* al matricii este o submatrice patratica complet inclusa in matricea $A$. Determinati latura maxima $LMAX$ a doua subpatrate identice din cadrul matricii, precum si numarul $P$ de perechi de subpatrate de latura $LMAX$ care sunt identice.
Petre si Paul joaca urmatorul joc. Initial, ei au la dispozitie un numar $N$. Pe parcursul jocului ei efectueaza mutari alternativ. O mutare consta in impartirea numarului $N$ la un numar $P$ ales de jucatorul aflat la mutare, cu restrictia: $2 ≤ P ≤ K$. In continuare, noua valoare a lui $N$ va fi $N/P$ (se ia parte intreaga inferioara din rezultat). Castiga jucatorul care, atunci cand ii vine randul, reduce numarul $N$ la $0$ (echivalent, pierde jucatorul care, atunci cand ii vine randul la mutare, are la dispozitie numarul $N=0$).
Determinati daca primul jucator are strategie sigura de castig (primul jucator = cel care efectueaza prima mutare).
h2. Date de intrare
Prima linie a fisierului de intrare $pp.in$ contine numerele intregi $M$ si $N$. Urmatoarele $M$ lini contin cate $N$ caractere din multimea ${'a'-'z'}$, neseparate prin spatii, descriind matricea $A$.
Prima (si singura) linie a fisierului de intrare $pp.in$ contine numerele intregi $N$ si $K$, separate printr-un spatiu.
h2. Date de iesire
Fisierul de iesire $pp.out$ va contine $2$ linii. Pe prima linie veti afisa valoarea $LMAX$, reprezentand latura maxima a doua subpatrate identice din matricea $A$. Pe a doua linie veti afisa numarul $P$, reprezentand numarul de perechi $(X,Y)$ de subpatrate de latura $LMAX$, astfel incat subpatratul $X$ este identic cu subpatratul $Y$.
Fisierul de iesire $pp.out$ va contine numarul intreg $A$, unde $A=1$, daca primul jucator are strategie sigura de castig, respectiv $A=0$, in caz contrar.
h2. Restrictii
* $1 ≤ M, N ≤ 500$
* Doua subpatrate identice de aceeasi latura se pot suprapune partial (dar nu total).
* $0 ≤ N ≤ 2.000.000.000$
* $2 ≤ K ≤ 100$
h2. Exemplu
table(example). |_. pp.in |_. pp.out |
|4 7
abcdefg
bcdefga
cdefgab
defgabc
|3
4
|1024 7
|1
|
== include(page="template/taskfooter" task_id="pp") ==
