perspico

Inspirată de faimosul Perspico, Miruna se gândeşte la următorul joc: se dă o matrice cu $N$ linii şi $M$ coloane în care fiecare număr între $0$ şi $N \cdot M - 1$ apare exact o singură dată. O mutare validă în acest joc constă din interschimbarea elementului $0$ cu unul dintre cei $4$ vecini ai săi. Miruna câştigă dacă reuşeşte să aducă matricea în următoarea configuraţie:

• Pe orice poziţie $(x, y)$, cu excepţia poziţiei $(N, M)$, trebuie să se găsească valoarea $(x - 1) \cdot M + y$;
• Pe poziţia $(N, M)$ trebuie să se găsească valoarea $0$.

Cerinţă

Fiind dată o configuraţie a jocului ajutaţi-o pe Miruna să îl termine, iar ea vă va răsplăti cu un pupic ;).

Date de intrare

Pe prima linie din fişierul de intrare perspico.in se află $2$ numere întregi $N$ şi $M$, având semnficaţia din enunţ. Următoarele $N$ linii vor conţine câte $M$ numere naturale, reprezentând elementele matricei.

Date de ieșire

În fişierul de ieşire perspico.out se vor scrie mai multe numere naturale din intervalul $[1, 4]$, reprezentând mutările efectuate, codificarea lor fiind următoarea:

• $1$ – Dacă elementul $0$ se interschimbă cu cel de deasupra.
• $2$ – Dacă elementul $0$ se interschimbă cu cel din dreapta.
• $3$ – Dacă elementul $0$ se interschimbă cu cel de dedesubt.
• $4$ – Dacă elementul $0$ se interschimbă cu cel din stânga.

Restricții și precizări

• $2 \leq N, M \leq 64$
• Dacă există mai multe soluţii poate fi afişată oricare.
• Se garantează că pe toate fişierele de test există cel puţin o soluţie.

Exemplu

perspico.in

3 3
0 1 3
4 2 6
7 5 8

perspico.out

3

Explicație

Mutările efectuate vor fi în direcţiile: E, S, S, E.
După efectuarea lor matricea va arăta astfel:

1 2 3
4 5 6
7 8 0