Octav e încă mititel, dar merge la grădiniță. Acolo a învăţat să deseneze diferite modele geometrice pe foi dreptunghiulare de matematică. Foaia de matematică are N x M pătrăţele organizate pe N linii (numerotate de sus în jos de la 1 la N) şi M coloane (numerotate de la stânga la dreapta de la 1 la M). Astfel, orice pătrăţel de pe foaie poate fi identificat prin numărul liniei şi numărul coloanei pe care se află acesta.

Octav începe din colțul stânga-sus al foii de matematică (pătrăţelul 1, 1) și merge diagonal în jos, marcând cu x fiecare pătrățel prin care trece. Când ajunge la una dintre marginile foii, el schimbă direcţia şi sensul de deplasare, ca în imaginile următoare.

El se deplasează continuu, marcând cu x pătrăţelele prin care trece, până când ajunge din nou într-un colț al foii. Octav consideră că pătrăţelele marcate cu x sunt ziduri.

Pătrăţelele marcate cu x delimitează pe foaia de matematică diferite modele geometrice. Un model este o zonă maximală (care nu mai poate fi extinsă) de pătrățele nemarcate, cu proprietatea că putem ajunge de la orice pătrățel al zonei la oricare altul efectuând doar deplasări pe direcțiile sus, jos, stânga, dreapta, fără a trece prin zid.

Aria unui model este egală cu numărul de pătrăţele din care este format modelul.

Două modele A și B sunt considerate egale dacă putem deplasa imaginar modelul A peste modelul B, fără a-l roti, astfel încât cele două să se suprapună perfect (orice pătrățel din A să fie peste un pătrățel din B și niciun pătrățel din B să nu rămână neacoperit). Observăm că relația de egalitate este simetrică.

Octav analizează cu atenţie modelele obţinute şi le grupează pe categorii. O categorie este formată din toate modelele egale pe care le-a obţinut.

Pătrăţelul reprezentativ al unei categorii este pătrăţelul cu cea mai mică poziţie care aparţine unui model din categoria respectivă.

Spunem că poziţia (lin1, col1) este mai mică decât poziţia (lin2, col2) dacă (lin1 < lin2) sau (lin1 = lin2 şi col1 < col2).

Descrierea unei categorii este constituită din patru valori a nr lin col, unde a este aria fiecărui model din categoria respectivă, nr reprezintă numărul de modele din categorie, iar (lin, col) reprezintă poziţia pătrăţelului reprezentativ al categoriei respective.

Cerința

Cunoscând numerele naturale N şi M, scrieţi un program care să rezolve următoarele cerinţe:
1. determină numărul de pătrăţele marcate cu x;
2. determină numărul total de modele obţinute;
3. determină numărul de categorii obţinute;
4. determină descrierile categoriilor de modele obţinute, ordonate crescător după pătrăţelul reprezentativ.

Date de intrare

Fișierul de intrare model.in conține pe prima linie trei numere naturale separate prin câte un spaţiu C N M, reprezentând cerinţa care trebuie să fie rezolvată (1, 2, 3 sau 4), numărul de linii, respectiv numărul de coloane de pe foaia de matematică.

Date de ieșire

Fișierul de ieșire model.out conține:

• dacă 1 ≤ C ≤ 3: un număr natural reprezentând răspunsul la cerinţa C;
• dacă C = 4: descrierile categoriilor obţinute, în forma descrisă în enunţ, câte o categorie pe o linie, ordonate crescător după pătrățelul reprezentativ.

Restricții și precizări

• 2 ≤ N, M ≤ 500
• Pentru 12 puncte, C = 1
• Pentru 28 de puncte, C = 2
• Pentru 21 de puncte, C = 3
• Pentru 39 de puncte, C = 4

Exemplul 1:

model.in

1 10 13

model.out

34

Exemplul 2:

model.in

2 10 13

model.out

10

Exemplul 3:

model.in

3 10 13

model.out

7

Exemplul 4:

model.in

4 10 13

model.out

9 2 1 2
9 1 2 1
13 3 2 7
9 1 2 13
6 1 8 1
9 1 8 7
6 1 8 13

Explicații

Pe foaia de matematică există 10 x 13 pătrăţele, organizate pe 10 linii şi 13 coloane.

Numărul de pătrăţele marcate cu \texttt{x} este 34.
Numărul total de modele obţinute este 10.
Numărul total de modele distincte obţinute este 7.
Descrierile celor 7 categorii de modele sunt: