Pentru suprafaţă de teren de formă pătrată, un topograf trebuie să alcătuiască o hartă amănunţită. El va împărţi mai întâi pătratul în 256 de pătrate egale, mai mici, pe care le numerotează de la 0 la 255: cele 16 pătrate de pe prima linie sunt astfel numerotate de la 0 la 15, cele 16 pătrate de pe a doua linie sunt numerotate de la 16 la 31, ş.a.m.d. Aceste 256 de pătrate le numeşte pătrate de tip 1 şi fiecare este identificat unic prin numărul său. În a doua etapă va lua fiecare pătrat de tip 1 şi-l va împărţi în 25 de pătrate egale, pe care le numeşte pătrate de tip 2. Acestea vor fi „numerotate” cu litere mari ale alfabetului, deci de la ’A’ la ’Y’: prima linie va avea asociate literele ’A ’, ’B ’, ’C ’, ’D ’, ’E ’, a doua linie ’F ’, ’G ’, ’H ’, ’I ’, ’J ’ ş.a.m.d. Fiecare pătrat de tip 2 se împarte în 1024 de pătrate egale (numite de tip 3), fiecare pătrat fiind numerotat cu numere de la 0 la 1023 după acelaşi principiu ca mai sus. În fine, fiecare pătrat de tip 3 se împarte în 16 pătrate de tip 4, numerotate cu litere mici ale alfabetului, deci de la ‘a’ la ’p’: prima linie de 4 pătrate va fi numerotată cu ’a’, ‘b’, ‘c’, ‘d’, a doua cu ‘e’, ‘f’, ‘g’, ‘h’ ş.a.m.d. Fiecare pătrat de tip 4 va fi unic identificat prin coordonatele sale, adică prin 4 valori (x1, x2, x3, x4), unde x1 este un număr între 0 şi 255 şi este numărul asociat pătratului de tip 1 în care se află pătratul de tip 4, x2 este litera asociată pătratului de tip 2 (deci ’A’ <= x2 <= ’Y’), x3 este numărul asociat pătratului de tip 3 (deci este o valoare între 0 şi 1023), iar x4 este litera mică asociată pătratului de tip 4 (deci una din literele de la ‘a’ la ‘p’).
Această împărţire detaliată face ca unui pătrat de tip 4 să îi corespundă în teren o locaţie pe care se poate afla o entitate precum: un copac, o tufă, un mic dâmb etc. Locaţiile mai multor entităţi alăturate în teren (de exemplu copacii unei păduri) corespund pe hartă unor pătrate de tip 4 învecinate pe linii sau coloane şi care, împreună, formează un singur obiectiv. Dimensiunea obiectivului este dată de numărul de pătrate de tip 4 alăturate care îl compun. Topograful şi-a notat coordonatele pătratelor de tip 4 care corespund unor locaţii din teren pe care se află câte o entitate.
Cerinţă
Dându-se locaţia precisă a acestor entităţi din teren, ajutaţi-l pe topograf să determine numărul de obiective care se pot forma precum şi dimensiunea celui mai mare obiectiv.
Date de intrare
Fişierul de intrare harta.in conţine pe prima linie un număr natural N, reprezentând numărul de entităţi din teren. Pe fiecare dintre următoarele N linii se vor găsi patru valori x1, x2, x3, x4 separate prin câte un spaţiu, care reprezintă coordonatele unei entităţi.
Date de ieşire
Fişierul harta.out va conţine pe prima linie două numere naturale separate prin spatiu P şi Q reprezentând numărul de obiective din teren respectiv dimensiunea celui mai mare obiectiv.
Restricţii
1 <= N <= 5 000
0 <= x1 <= 255
'A' <= x2 <= 'Y'
0 <= x3 <= 1023
'a' <= x4 <= 'p'
Oricare două pătrate date în fişierul de intrare sunt distincte
Două pătrate de tip 4 sunt vecine dacă au o latură comună
Exemple
harta.in
harta.out
Explicaţii
7
11 B 34 e
190 D 18 k
11 B 33 h
67 M 0 m
11 B 34 a
190 D 18 g
11 B 34 b
3 4
Sunt 3 obiective. Primul este format din pătratele de tip 4 de la coordonatele (11,B,34,a), (11,B,34,b), (11,B,34,e), (11,B,33,h). Al doilea obiectiv este format din (190,D,18,k) şi (190,D,18,g). Ultimul obiectiv este format dintr-o singură entitate, cea din pătratul (67,M,0,m). Cel mai mare obiectiv este format din 4 entităţi.
harta.in
harta.out
Explicaţii
7
5 H 31 c
5 C 1023 o
5 H 31 g
5 H 31 k
5 H 31 o
5 H 63 c
5 H 63 f
2 6
Sunt două obiective. Primul este format cu primele 6 pătrate, iar al doilea dintr-un singur pătrat, ultimul. De remarcat faptul că pătratul de la coordonatele (5,C,1023,o) se învecinează „la sud” cu pătratul de la coordonatele (5,H,31,c). La fel şi pătratele (5,H,31,o), (5,H,63,c).
Se observă că pătratul de coordonate (5,H,63,f) nu se învecinează cu pătratul (5,H,63,c), deoarece nu au o latură comună.