model

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 \times 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 imaginea 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 $(lin_1, col_1)$ este mai mică decât poziția $(lin_2, col_2)$ dacă ($lin_1 < lin_2$) sau ($lin_1 = lin_2$ și $col_1 < col_2$).

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țe

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 \leq C \leq 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 \leq N, M \leq 500$

Exemplul 1

model.in

1 10 13

model.out

34

Explicație

În toate cele 4 exemple, pe foaia de matematică există $10 \times 13$ pătrățele, organizate pe $10$ linii și $13$ coloane, astfel:

După cum se vede, numărul de pătrățele marcate cu x este $34$.

Exemplul 2

model.in

2 10 13

model.out

10

Explicație

Numărul total de modele obținute este $10$.

Exemplul 3

model.in

3 10 13

model.out

7

Explicație

Numărul total de modele distincte obținute este $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ție

Descrierile celor $7$ categorii de modele sunt: