gradina

Într-o grădină botanică zonele în care se găsesc plante aparţinând aceleaşi specii sunt înconjurate de gard viu, de grosime neglijabilă. O specie ocupă o singură zonă. Suprafaţa grădinii, de formă dreptunghiulară, este împărţită în porţiuni de $1 \times 1$. Fiecare porţiune poate avea (sau nu) pe fiecare din laturile dinspre V, N, E sau S gard viu.

Cerinţă

Cunoscând planul codificat al grădinii determinaţi:

• numărul speciilor de plante ce se găsesc în grădină;
• suprafaţa maximă ocupată de o singură specie;
• suprafaţă de arie maximă ce se poate obţine prin unirea a două zone, precum şi poziţia porţiunii de gard (de dimensiune $1$) prin a cărei îndepărtare se obţine această suprafaţă.

Date de intrare

Fişierul de intrare gradina.in are structura:

• $n \ m$
• $a_{1_1} \ a_{1_2} \dots a_{1_m}$
• $a_{2_1} \ a_{2_2} \dots a_{2_m}$
• $\dots$
• $a_{n_1} \ a_{n_2} \dots a_{n_m}$

unde

• $n, m$ - lungimea respectiv lăţimea grădinii exprimate în metri
• $a_{1_1} \ a_{1_2} \dots a_{1_m}$ - descriere linia $1$ pentru planul grădinii
• $a_{2_1} \ a_{2_2} \dots a_{2_m}$ - descriere linia $2$ pentru planul grădinii
• $\dots$
• $a_{n_1} \ a_{n_2} \dots a_{n_m}$ - descriere linia $n$ pentru planul grădinii

unde $a_{ij}$ reprezintă codificările porţiunilor din suprafaţa grădinii, astfel:

• $0$ daca nu are gard viu pe nici una din laturile V,N,E,S
• la codificare se adaugă:
  • $1$ dacă există gard viu spre V
  • $2$ dacă există gard viu spre N
  • $4$ dacă există gard viu spre E
  • $8$ dacă există gard viu spre S

Date de ieșire

Fişierul de ieşire gradina.out are structura:

• $N_s$
• $A_{max}$
• $aria \ l_{max} \ c_{max} \ d_{max}$

unde

• $N_s$ - numărul speciilor de plante
• $A_{max}$ - aria maximă
• $aria \ l_{max} \ c_{max} \ d_{max}$ - aria ce se obţine prin unirea a două zone, linia, coloana şi latura (N, E, S, V) porţiunii de gard ce trebuie eliminată, separate prin câte un spaţiu.

Restricții și precizări

• $1 \leq N, M \leq 20$
• în cazul în care există mai multe soluţii de obţinere a ariei maxime se va indica cea pentru care numărul liniei zonei eliminate este minim, iar dacă există mai multe soluţii cu numărul de linie minim, cea care are numărul coloanei minim
• Dacă întreaga suprafață este acoperită de o singură specie, se va afișa $0 \ 0 \ 0 \ X$

Exemplul 1

gradina.in

4 5
3 6 15 3 6
1 0 14 1 4
9 12 7 9 12
11 10 12 11 14

gradina.out

5
7
13 2 3 E

Explicație

Configuraţia iniţială a grădinii (pentru exemplul dat) şi după unirea celor două zone detectate: