Arheologii au descoperit pe un platou muntos greu accesibil ruinele unui castel medieval, pe care l-au fotografiat din elicopter, obţinând harta digitizată a acestuia. Harta este memorată sub forma unui tablou bidimensional H, compus din N x N pătrate cu latura egală cu unitatea, având ca elemente numere naturale între 0 și 15, care codifică forma pereţilor fiecărui pătrat unitar. Dacă scriem numărul natural H[i][j] în baza 2, folosind exact 4 cifre binare, fiecare bit dă informații despre unul dintre pereții posibil de construit pe fiecare latură a pătratului unitar din poziția (i,j), astfel:

• dacă bitul de pe poziția 0 are valoarea 1, atunci există perete pe latura vestică (latura din stânga);
• dacă bitul de pe poziția 1 are valoarea 1, atunci există perete pe latura sudică (latura de jos);
• dacă bitul de pe poziția 2 are valoarea 1, atunci există perete pe latura estică (latura din dreapta);
• dacă bitul de pe poziția 3 are valoarea 1, atunci există perete pe latura nordică (latura de sus);
• un bit de valoare 0 indică lipsa peretelui corespunzător acestuia;

Pentru un număr scris în baza 2, numerotarea cifrelor începe cu poziția 0, de la dreapta la stânga.
Castelul este interesant deoarece, pentru realizarea unei mai bune apărări, camerele ce-l compun sunt construite fie independent, fie una în interiorul alteia. Orice camera este construită la o distanţă de cel puţin o unitate faţă de zidul ce împrejmuieşte castelul sau faţă de pereţii altor camere.
Folosind harta, arheologii doresc să afle informaţii privind numărul camerelor şi camera de arie maximă. Prin arie a unei camere se înţelege numărul pătratelor unitate cuprinse în interiorul pereților aceasteia, fără a socoti ariile camerelor construite în interiorul ei.

Cerința

Cunoscând codificarea hărţii castelului, să se determine:
1. numărul total al camerelor din castel
2. aria maximă a unei camere
3. coordonatele colţurilor din stânga-sus, respectiv dreapta-jos a camerei cu aria maximă. Dacă există mai multe camere având aceeaşi arie maximă, atunci se vor afişa coordonatele camerei având colţul din stânga-sus (lin1, col1) cu lin1 minimă, iar la linii egale pe aceea cu col1 minimă.

Date de intrare

Datele de intrare se citesc din fişierul castel1.in, care are următoarea structură:
- Pe prima linie se află numărul natural C, care poate fi egal cu 1, 2 sau 3, în funcţie de cerinţa ce trebuie rezolvată;
- Pe linia următoare se află numărul natural N, reprezentând dimensiunea hărţii;
- Pe următoarele N linii se găsesc câte N numere naturale din intervalul [0,15], separate prin câte un spaţiu, reprezentând harta castelului.

Date de ieșire

Datele de ieşire se vor scrie în fişierul castel1.out, astfel:
- Dacă C = 1, pe prima linie se va scrie numărul total al camerelor din castel;
- Dacă C = 2, pe prima linie se va scrie aria maximă a unei camere din castel;
- Dacă C = 3, pe prima linie se vor scrie patru numere naturale lin1 col1 lin2 col2, separate prin câte un spaţiu, reprezentând coordonatele colțurilor din stânga-sus, respectiv dreapta-jos ale camerei de arie maximă.

Restricții și precizări

• 2 < n ≤ 100
• Se garantează că în castel există cel puţin o cameră;
• Testele care au C = 1 totalizează 20 de puncte;
• Testele care au C = 2 totalizează 50 de puncte;
• Testele care au C = 3 totalizează 20 de puncte;
• În concurs s-au acordat 10 puncte din oficiu. Aici se vor acorda pentru exemplele din enunț.

Exemplul 1:

castel1.in

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

castel1.out

6

Explicație

În figură este reprezentată harta castelului codificat în fișierul de intrare. Acesta conține 6 camere.

Exemplul 2:

castel1.in

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

castel1.out

11

Explicație

Aria maximă a unei camere este 11.

Exemplul 3:

castel1.in

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

castel1.out

5 5 7 8

Explicație

Camera cu aria maximă are coordonatele (5,5) – (7,8).