Ferma

Un fermier deține o fermă de formă dreptunghiulară cu lungimea $m$ metri și lățimea $n$ metri. Respectând principiul rotației culturilor, fermierul și a realizat un plan pentru semănarea culturilor în noul an. Astfel, el a desenat un dreptunghi pe care l-a împărțit în $m \cdot n$ celule, fiecare corespunzând unui metru pătrat, și a colorat în culori diferite zonele care corespund unor culturi diferite. O cultură poate fi semănată pe mai multe parcele. Două celule care au o latură comună aparțin aceleiași parcele dacă au aceeași culoare (sunt însămânțate cu aceeași cultură). Fermierul are posibilitatea să irige o sigură parcelă și dorește să aleagă parcela cu cea mai mare suprafață. Nefiind mulțumit de suprafața rezultată, s-a întrebat dacă ar putea schimba cultura de pe o singură celulă, astfel încât să obțină o parcelă de suprafață mai mare.

Exemplu de fermă (imagine 1):

Cerință

Dându-se dimensiunile fermei și pentru fiecare celulă culoarea corespunzătoare culturii semănate, determinați:

1. Varianta 1: Suprafața maximă a unei parcele în planul inițial.
2. Varianta 2: Numărul liniei, respectiv al coloanei celulei pe care va semăna o altă cultură și culoarea corespunzătoare noii culturi în vederea obţinerii celei mai mari parcele posibile.

Date de intrare

Fișierul de intrare ferma.in va conține:]

• pe prima linie un număr natural $v$ ($1 ≤ v ≤ 2$) indicând varianta cerinței de rezolvare
• pe a doua linie două numere naturale $m$ şi $n$ separate printr-un spațiu, cu semnificația din enunț
• pe fiecare dintre următoarele $m$ linii se găsesc câte $n$ caractere (litere mici), reprezentând codurile culturilor ce vor fi semănate pe cele $n$ celule corespunzătoare fiecărei linii.

Date de ieșire

Fișierul de ieșire ferma.out va conține:
Varianta 1 – pentru $v=1$:

• pe prima linie numărul natural $s$, reprezentând suprafața maximă a unei parcele.

Varianta 2 – pentru $v=2$:

• pe prima linie două numere naturale separate printr-un spațiu, reprezentând numărul liniei, respectiv al coloanei celulei pe care va semăna o altă cultură, în vederea obținerii unei parcele cu suprafața maximă;
• pe a doua linie un caracter reprezentând codul culorii corespunzătoare noii culturi din celula determinată.

Restricții și precizări

• $2 \leq n, m \leq 400$
• Numărul de culturi distincte este cel puţin $2$ şi cel mult $26$.
• $30\%$ din teste vor avea pe prima linie valoarea $1$, iar restul de $70\%$ din teste vor avea pe prima linie valoarea $2$.
• Pentru varianta $2$ se punctează orice soluție care conduce la obținerea unei parcele cu suprafața maximă. Nu se acordă punctaje parțiale.

Exemplul 1

ferma.in

1
7 8
rmmgggaa
mvvgggaa
mvvgvvvv
vvvrvvvv
vvrrrgga
vvrrrggg
aaaaaaag

ferma.out

11

Explicație

Această imagine corespunde ambelor exemple.

În varianta 1 se determină și se afișează suprafața maximă a unei parcele, care este egală cu $11$ și corespunde parcelei $6$, de culoare verde (codificată cu litera $v$ în imaginea 1 şi în fişierul de intrare).

Exemplul 2

ferma.in

2
7 8
rmmgggaa
mvvgggaa
mvvgvvvv
vvvrvvvv
vvrrrgga
vvrrrggg
aaaaaaag

ferma.out

3 4
v

Explicație

Pentru varianta 2:
Schimbând în verde ($v$) culoarea celulei de pe linia $3$ şi coloana $4$, se obține o parcelă cu suprafața $11+8+1=20$ (se unesc parcelele cu numărul $6$ respectiv $8$).

O altă soluţie corectă este:
$4 \ 4$
$v$