Fişierul intrare/ieşire:	piese.in, piese.out	Sursă	preONI 2008 Runda 3
Autor	Filip Cristian Buruiana	Adăugată de	Filip Cristian Buruiana •filipb
Timp execuţie pe test	0.05 sec	Limită de memorie	8192 kbytes
Scorul tău	N/A	Dificultate	N/A

Piese

Danut nu a descoperit inca informatica si se joaca cu piese de diferite dimensiuni. Piesele sale sunt de forma patratica si au latura o putere a lui 2. Astfel, Danut are piese de dimensiuni 1×1, 2×2, 4×4, 8×8, etc. Putem considera ca Danut are un numar nelimitat de piese din fiecare tip. Sarcina lui este acum sa acopere cu aceste piese o tabla de dimensiuni M x N. El stie ca orice patratel al tablei trebuie sa fie acoperit de exact o piesa. Pentru ca vrea sa realizeze acoperirea cu efort minim, Danut vrea sa foloseasca un numar minim de piese.

Date de intrare

Fisierul de intrare piese.in contine pe prima linie numerele M si N, cu semnificatia din enunt.

Date de iesire

In fisierul de iesire piese.out se va scrie pe prima linie MIN, numarul minim de piese folosit. Fiecare din urmatoarele M linii contine cate N numere ce descriu acoperirea cu piese a tablei. Oricare piesa va avea asociat un numar natural unic de la 1 la MIN. Astfel, al j-lea numar de pe linia i+1 (i de la 1 la M, j de la 1 la N) reprezinta numarul piesei care acopera patratelul de coordonate (i j) de pe tabla. Daca sunt mai multe solutii cu numar minim de piese se poate afisa oricare.

Restrictii

1 ≤ M, N ≤ 500
Punctajul pe un test nu se acorda decat daca acoperirea cu piese este corecta (este folosit un numar minim de piese de tipul celor descrise mai sus si tabla este acoperita in intregime)