pictura

Robotul Vasile se visează artist plastic. El creează picturi 3D, pe un suport pe care îl scoate la imprimantă. O pictură 3D are formă dreptunghiulară şi poate fi împărţită în „pixeli 3D”, aranjaţi pe n linii şi m coloane, fiecare pixel 3D având o anumită înălţime. Iniţial pictura este albă.

Un pixel 3D este considerat „vârf” dacă el are înălţimea strict mai mare decât înălțimile tuturor vecinilor săi. Doi pixeli 3D se consideră vecini dacă ei se află pe aceeaşi linie, pe coloane consecutive, sau se află pe aceeaşi coloană, pe linii consecutive.

Robotul Vasile pictează algoritmic, în modul următor: parcurge pixelii în ordinea liniilor, iar pe fiecare linie în ordinea coloanelor şi dacă pixelul curent este un vârf „toarnă” peste el o nouă culoare (o culoare diferită de alb şi de toate culorile utilizate până la momentul respectiv). Vom denumi culori pure, culorile pe care robotul Vasile le toarnă peste pixelii vârf. Culoarea pură se va „scurge” şi va vopsi toţi pixelii 3D vecini care au înălţime strict mai mică decât a vârfului vopsit, apoi se va scurge în continuare la vecinii vecinilor cu înălţimi strict mai mici ş.a.m.d., până când scurgerea nu mai este posibilă. Atunci când culoarea pură ajunge peste un pixel alb, acesta se va colora în culoarea respectivă. Dacă însă culoarea pură ajunge peste un pixel care a fost colorat anterior, culorile se vor combina şi se va crea o nouă culoare. Culorile care se formează prin combinare vor fi diferite de toate culorile pure pe care robotul Vasile le toarnă peste pixelii vârf.

Deşi se visează artist, robotul Vasile nu are simţ estetic, ca urmare a stabilit trei criterii de evaluare a calităţii artistice a unei picturi: numărul maxim de culori pure care se combină pe un pixel 3D, numărul de culori distincte care apar în pictură (pure sau obținute prin combinare), respectiv dimensiunea maximă a unei zone colorate în aceeaşi culoare, diferită de alb. O zonă este formată din pixeli 3D cu proprietatea că, pentru oricare doi pixeli $p_1$ şi $p_2$ din zona respectivă există o succesiune de pixeli 3D care începe cu $p_1$, se termină cu $p_2$ şi oricare doi pixeli consecutivi sunt vecini. Dimensiunea unei zone este egală cu numărul de pixeli 3D din zona respectivă.

Cerință

Scrieţi un program care, cunoscând $n$ şi $m$(dimensiunile picturii), respectiv înălţimile pixelilor 3D, rezolvă următoarele trei cerinţe:

1. determină numărul maxim de culori pure care se combină pe un pixel 3D;
2. determină numărul de culori distincte care apar în pictura creată conform algoritmului aplicat de robotul Vasile;
3. determină dimensiunea maximă a unei zone formată din pixeli 3D de aceeaşi culoare, diferită de alb.

Date de intrare

Fişierul de intrare pictura.in conţine pe prima linie trei numere naturale $C \ n \ m$, reprezentând cerinţa care trebuie să fie rezolvată ($1$, $2$ sau $3$), numărul de linii, respectiv numărul de coloane ale picturii. Pe fiecare dintre următoarele $n$ linii se află câte𝑚numere naturale reprezentând înălţimile pixelilor 3D care constituie suprafaţa pe care pictează robotul Vasile (respectând ordinea liniilor, respectiv a coloanelor). Valorile scrise pe aceeaşi linie sunt separate prin câte un spaţiu.

Date de ieșire

Fişierul de ieşire pictura.out va conţine o singură linie pe care va fi scris răspunsul la cerinţa $C$ din fişierul de intrare.

Restricții și precizări

• $3 \leq n,m \leq 300$
• Înălţimile pixelilor 3D sunt numere naturale $\leq 30 \ 000$.
• Pentru toate datele de test se garantează că numărul de culori pure care se combină pe un același pixel 3D este $< 200$.

Exemplul 1

pictura.in

1 5 3
8 7 8
8 20 18
11 5 30
19 4 50
2 3 40

pictura.out

3

Exemplul 2

pictura.in

2 5 3
8 7 8
8 20 18
11 5 30
19 4 50
2 3 40

pictura.out

7

Exemplul 3

pictura.in

3 5 3
8 7 8
8 20 18
11 5 30
19 4 50
2 3 40

pictura.out

4

Explicații

Înălţimile pixelilor 3D sunt ilustrate în figura $1$, vârfurile fiind marcate îngroşat (înălţimile acestora fiind $20, 19, 50$). Toți pixelii au inițial culoarea albă, marcată cu $0$.

Vom colora succesiv cele $3$ vârfuri. Colorând vârful cu înălţimea $20$ în culoarea $1$ obţinem imaginea din figura $2$.
Colorând vârful cu înălţimea $19$ în culoarea $2$ obţinem imaginea din figura $3$, unde am notat cu $(1, 2)$ combinaţia culorilor $1$ şi $2$.
Colorând vârful cu înălţimea $50$ în culoarea $3$ obţinem imaginea din figura $3$, unde am notat cu $(1, 3)$ combinaţia culorilor $1$ şi $3$, iar cu $(1, 2, 3)$ combinaţia culorilor $1, 2$ şi $3$.

Sunt vizibile $7$ culori distincte: $0, 1, 2, 3, (1, 2), (1, 3)$ şi $(1, 2, 3)$. Numărul maxim de culori pure care se combină pe un același pixel 3D este $3$. Dimensiunea maximă a unei zone formată din pixeli de aceeaşi culoare este $4$ - zona colorată în culoarea $(1, 2, 3)$.