harta

Pe baza unei imagini preluate din satelit, se realizează harta unei mici localități. Localitatea ocupă o suprafață dreptunghiulară, cu laturile orientate pe direcțiile Nord-Sud, respectiv Est-Vest. Studiind imaginea obținută de la satelit, cartografii au constatat că toate cele $k$ clădiri au forma unor dreptunghiuri distincte. Imaginea poate fi reprezentată sub form a unui tablou cu $n \cdot m$ celule așezate pe $n$ linii numerotate de la $1$ la $n$ și $m$ coloane numerotate de la $1$ la $m$.

Numim drum, un dreptunghi al tabloului care străbate întreaga localitate pe direcția Est-Vest și are un număr maxim de linii sau un dreptunghi care străbate întreaga localitate pe direcția Nord-Sud și are un număr maxim de coloane. Drumurile, evident, nu trebuie să treacă prin clădiri.

Cartografii sunt interesați ca pe această hartă să fie reprezentate la scară doar clădirile, nu și drumurile. De aceea, pentru realizarea hărții, lățimile drumurilor au fost reduse la o singură celulă.

Tabloul care reprezintă imaginea localității se codifică astfel: $1$ pentru o celulă ocupată de o clădire și $0$ pentru o celulă neocupată.

Cerință

Cunoscând $n$, $m$ și $k$, precum și tabloul care codifică imaginea, se cere să se determine:

1. Numărul $S$ de celule ocupate de către clădirea pătratică cu latura maximă și numărul de clădiri $C$ alese dintre celelalte $k–1$ clădiri, cu proprietatea că fiecare dintre ele "încape" în interiorul clădirii pătratice cu latură maximă, fără să se suprapună peste celulele marginale ale acesteia.
2. Tabloul care reprezintă harta, în urma prelucrării imaginii inițiale.

Date de intrare

Fişierul de intrare harta.in conţine pe prima linie un număr natural $p$. Pentru toate testele de intrare, numărul $p$ poate avea doar valoarea $1$ sau valoarea $2$.

Pe linia a doua se găsesc numerele naturale $n$, $m$ și $k$ separate prin câte un spațiu.

Pe fiecare dintre următoarele $k$ linii, se găsesc câte patru numere naturale $i_1$, $j_1$, $i_2$, $j_2$, separate prin câte un spațiu, primele două numere reprezentând coordonatele celulei din extremitatea Nord-Vest, iar ultimele două, coordonatele celulei din extremitatea Sud-Est pentru fiecare dintre cele $k$ clădiri.

Date de ieșire

• Dacă valoarea lui $p$ este $1$ atunci se va rezolva numai cerința 1. În acest caz, în fişierul de ieşire harta.out se vor scrie cele două numere $S$ și $C$ având semnificația descrisă la cerința 1, separate printr-un singur spațiu.
• Dacă valoarea lui $p$ este $2$, atunci se va rezolva numai cerința 2. În acest caz, fişierul de ieşire harta.out va conține tabloul care reprezintă harta obținută pe baza imaginii din satelit. Fișierul va avea $n_1$ linii. Pe fiecare linie se vor găsi câte $m_1$ valori $0$ sau $1$ separate prin câte un singur spațiu. Celulele situate pe marginile clădirilor vor avea valoarea $1$. Celulele din interiorul clădirilor, ca și cele din exterior, vor avea valoarea $0$.

Restricții și precizări

• $3 \leq n, m \leq 1 \ 500$
• $1 \leq i_1 \leq i_2 \leq n$
• $1 \leq j_1 \leq j_2 \leq m$
• $1 \leq k \leq 1\ 000$
• Latura maximă a oricărui dreptunghi este un număr natural cuprins între $1$ și $50$.
• Se garantează că există soluție pentru ambele cerințe, pentru toate datele de test.
• Pentru rezolvarea corectă a primei cerinţe se acordă $20$ de puncte, iar pentru cerința a doua se acordă $80$ de puncte.

Exemplul 1

harta.in

1
7 7 4
1 1 4 4
6 2 6 4
3 6 3 6
6 6 7 7

harta.out

16 2

Explicație

Atenție! Pentru acest test se rezolvă doar cerința 1.

Clădirea de coordonate $(1 \ 1 \ 4 \ 4)$ este cel mai mare pătrat și ocupă $S=4 \cdot 4 = 16$ celule. Clădirile de coordonate $(3 \ 6 \ 3 \ 6)$ și $(6 \ 6 \ 7 \ 7)$ "încap" în interiorul clădirii $(1 \ 1 \ 4 \ 4)$ fără să se suprapună peste celulele sale marginale. Deci $C = 2$.

Exemplul 2

harta.in

2
10 11 4
1 2 4 4
8 9 8 9
7 3 9 5
2 9 3 9

harta.out

0 1 1 1 0 0 0 0
0 1 0 1 0 0 1 0
0 1 0 1 0 0 1 0
0 1 1 1 0 0 0 0
0 0 0 0 0 0 0 0
0 0 1 1 1 0 0 0
0 0 1 0 1 0 1 0
0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 0

Explicație

Atenție! Pentru acest test se rezolvă doar cerința 2.

În imagine sunt $5$ drumuri determinate de dreptunghiurile: $(1 \ 1 \ 10 \ 1)$, $(1 \ 6 \ 10 \ 8)$, $(1 \ 10 \ 10 \ 11)$, $(5 \ 1 \ 6 \ 11)$ și $(10 \ 1 \ 10 \ 11)$.

Pe hartă, cele $5$ drumuri vor avea coordonatele: $(1 \ 1 \ 9 \ 1)$, $(1 \ 6 \ 9 \ 6)$, $(1 \ 8 \ 9 \ 8)$, $(5 \ 1 \ 5 \ 8)$ și $(9 \ 1 \ 9 \ 8)$.