Castel

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 \cdot 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ță

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 $({lin}_1, {col}_1)$ cu ${lin}_1$ minimă, iar la linii egale pe aceea cu ${col}_1$ minimă.

Date de intrare

Datele de intrare se citesc din fişierul castel.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 castel.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 $4$ numere naturale ${lin}_1 \ {col}_1 \ {lin}_2 \ {col}_2$, 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 \leq N \leq 100$;
• Se garantează că în castel există cel puţin o cameră.
• Se acordă $10$ puncte din oficiu.

Exemplul 1

castel.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

castel.out

6

Explicație

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

Exemplul 2

castel.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

castel.out

11

Explicație

Aria maximă a unei camere este $11$.

Exemplul 3

castel.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

castel.out

5 5 7 8 

Explicație

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