Rezolvare PBinfo #4475

Fermierul Petrică deține o livadă de formă dreptunghiulară, împărțită în N×M sectoare, dispuse pe N linii și M coloane, in fiecare sector fiind plantat un arbore dintr-o anumită specie, identificată printr-o literă mare a alfabetului englez.

Vecinul său, fermierul Ion dorește să cumpere o zonă dreptunghiulară din livada lui Petrică, care să aibă suprafața S și pentru fiecare specie prezentă în acea zonă numărul de arbori să fie același.

Cerința

Determinați în câte moduri se poate alege zona dorită de Ion, precum și o modalitate de alegere.

Date de intrare

Fișierul de intrare livada.in conține pe prima linie numerele N M S. Următoarele N linii conțin câte M litere mari ale alfabetului englez, separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire livada.out va conține pe prima linie numerele I J H L, separate prin câte un spațiu, unde I J reprezintă coordonatele colțului stânga sus al zonei alese, iar H L reprezintă înălțimea zonei (numărul de linii), respectiv lățimea zonei (numărul de coloane).

A doua linie a fisierului va conține un număr natural reprezentând numărul de modalități de a alege zona dorită de Ion.

Restricții și precizări

• 1 ≤ N, M ≤ 500;
• 1 ≤ S ≤ N*M;
• liniie și coloanele livezii sunt numerotate de începând de la 1;
• dacă nu există nicio posibilitate de a alege zona dorită de Ion fișierul de ieșire va conține numai valoarea 0;
• valorile I J H L vor fi alese astfel încât I să fie minim. Dacă există mai multe modalități de alegere cu I minim, se va alege aceea cu J minim. Dacă în continuare există mai multe modalități de alegere, se va alege aceea cu H minim;
• pentru teste în valoare de 30 de puncte, N,M ≤ 50.

Exemplu

livada.in

3 5 6
A A B A A
D D D D A
A B A D A

livada.out

1 2 3 2
2

Explicație

A A B A A
D D D D A
A B A D A

A A B A A
D D D D A
A B A D A