Astăzi, la finalul orei de informatică, profesorul a dat ca temă pentru acasă o problemă foarte dificilă, așa că elevii s-au hotărât să copieze unii de la alții. Vor trebui totuși să lucreze cât mai deștept pentru a nu fi prinși că au copiat.

Clasa este alcatuită din N x M elevi, așezați în bănci pe N rânduri și M coloane. Spunem că doi elevi sunt vecini dacă se află în bănci adiacente fie pe rânduri, fie pe coloane. Tema fiecărui copil constă în găsirea unui număr natural. Pentru ca elevii să nu fie prinși că au copiat, toate temele acestora vor trebui să fie distincte. Mai mult, elevii sunt foarte leneși, așa că își vor modifica tema foarte puțin față de tema vecinilor. Mai exact, tema oricarui elev diferă prin exact un bit în scrierea în baza 2 față de tema oricărui vecin al său. De exemplu 3 și 2 diferă prin exact un bit, pe când 2 și 4 diferă prin doi biți.

Cerința

Pentru a nu ridica suspiciuni prea mari, elevii doresc să creeze temele astfel încât cea mai mare valoare a unei teme să fie cât mai mică posibil. Fiind date dimensiunile clasei, N și M, contruiți o configurație a valorilor temelor fiecarui elev din clasă astfel încât profesorul să nu își dea seama că aceștia au copiat.

Date de intrare

Programul citește de la tastatură două numere separate printr-un singur spațiu, N și M cu semnificația de mai sus.

Date de ieșire

Datele de ieșire constau în afișarea configurației temelor fiecărui elev. La ecran se vor afla N rânduri, iar pe fiecare rând se vor afla M numere naturale separate printr-un spațiu. Acestea reprezintă răspunsurile copiilor, corespunzătoare poziției lor în clasă.

Restricții și precizări

• 1 ≤ N, M ≤ 2000
• Subtask 1 (7 puncte) – N = 1
• Subtask 2 (9 puncte) – N și M sunt puteri ale lui 2
• Subtask 3 (14 puncte) – N este putere a lui 2
• Subtask 1 (70 de puncte) – fără restricții suplimentare

Punctare

Această problemă acceptă și soluții parțiale, astfel se va acorda punctaj parțial pentru fiecare test, în funcție de cât de aproape de răspunsul optim este soluția dată folosind următoarea formulă:

\( S \cdot max(1 – \sqrt{\frac{\frac{G}{O} – 1}{3}}, 0) \)

Unde:

• S este punctajul testului
• G este răspunsul dat
• O este răspunsul optim

Atenție! O soluție care nu respectă toate cerințele problemei pentru un anumit test (toate numerele să fie distincte și oricare două numere adiacente să difere printr-un singur bit) va fi punctată cu 0 pe acel test.

Exemplu:

Intrare

3 3

Ieșire

5 4 6
1 0 2
9 8 10

Explicație

În această secțiune, indicele poziționat in dreapta-jos a numărului reprezintă baza în care este scris. Spre exemplu, opt poate fi scris drept 810 = 10002. Unul dintre răspunsurile optime pentru copii sunt date în urmatorul tabel:

Putem observa că între oricare două bănci adiacente numerele elevilor din acele bănci diferă cu exact un bit. Valoarea maximă a soluției este 10 și este răspunsul optim. Este evident că există și alte răspunsuri optime, spre exemplu soluția propusă dar oglindită vertical sau orizontal.

Una dintre soluțiile parțiale posibile în care maximul este 15 este:

Această soluție ar fi punctată, conform formulei de punctare, cu 59,1% din punctajul testului.