Pase

Fotbaliștii echipei naționale se antrenează pe un teren de formă dreptunghiulară. Pe acest teren au fost trasate $L$ linii orizontale și $C$ linii verticale, astfel încât între oricare două linii distanța să fie egală cu $1$ metru. Liniile au fost numerotate de sus în jos cu valori de la $1$ la $L$, iar coloanele au fost numerotate de la stânga la dreapta cu valori de la $1$ la $C$ și tot terenul este format din celule pătratice de latura $1$. Intersecția dintre o linie și o coloană o vom denumi punct. Un punct este specificat prin linia și coloana la intersecția cărora se află.

Fotbaliștii pot trimite pase doar dintr-un punct către un alt punct. O pasă poate trece prin unul sau mai multe puncte. Un punct prin care trece o pasă se va numi punct pasabil.

Antrenorul echipei de fotbal dorește realizarea unei aplicații care să analizeze pasele jucătorilor dintr-un meci pentru a îmbunătăți calitatea paselor date de fotbaliști de la un meci la altul.

Cerință

Cunoscând $P$ pase, specificate fiecare prin punctul de start și punctul de final, să se determine zonele pătratice din teren, de arie maximă și nenulă, care nu conțin în interior sau pe margini niciun punct pasabil.

Exemplu: $L = 8$, $C = 10$, $P = 6$ și pasele:

$(2, 2) \rightarrow (2, 9)$; $(2, 2) \rightarrow (4, 8)$; $(5, 3) \rightarrow (8, 7)$; $(1, 8) \rightarrow (4, 8)$; $(5, 2) \rightarrow (3, 9)$; $(7, 9) \rightarrow (5, 10)$ atunci există o singură zonă pătratică de arie maximă = $9$, care nu conține niciun punct pasabil, colorată în figură.

Date de intrare

Fișierul de intrare pase.in conține:

• pe prima linie numerele naturale $L$ și $C$, cu semnificația din enunț;
• pe a doua linie numărul natural $P$, reprezentând numărul de pase;
• pe următoarele $P$ linii sunt descrise cele $P$ pase, câte o pasă pe o linie, fiecare pasă fiind descrisă prin patru numere naturale $a \ b \ c \ d$, unde $a \ b$ reprezintă linia, respectiv coloana punctului de start, iar $c \ d$ linia, respectiv coloana punctului de final $(1 \leq a, c \leq L, 1 \leq b, d \leq C)$.

Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire pase.out va conține, pe prima linie, numărul $Z$ de zone de arie pătratică maximă determinate și pe a doua linie aria $A$ unei astfel de zone. Pe următoarele $Z$ linii zonele determinate, câte o zonă pe o linie; o zonă va fi specificată prin $4$ numere naturale separate prin spațiu, reprezentând coordonatele punctului (linie, coloană) din colțul stânga-sus al zonei și coordonatele punctului (linie, coloană) din colțul dreapta-jos al zonei. Afișarea se va face în ordinea crescătoare a liniilor colțului din stânga-sus al zonei pătratice, iar pentru două linii egale în ordinea crescătoare a coloanei.

Restricții și precizări

• $1 \leq L, C \leq 1 \ 000$
• $1 \leq P \leq 1 \ 000$
• Se pot trimite pase de la un punct la același punct (cu mult efect!)
• Se garantează că pentru datele de test există soluție de arie nenulă.

Exemplu

pase.in

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

pase.out

1
9
4 4 7 7

Explicație

Datele din fișierul de intrare corespund imaginii precedente.

Există o singură zonă pătratică de arie maximă egală cu $9$, având colțul din stânga-sus $(4, 4)$ și colțul din dreapta-jos $(7, 7)$