Problem description
Jasio przeszedł właśnie kolejny poziom w swojej nowej grze logicznej Świadek. Nie chciał przerywać dobrej passy, więc spróbował rozwiązać kolejną zagadkę. Ma ona następującą postać:
Dany jest obrazek, który podzielono na kwadratowe kafelki w taki sposób, że powstało N wierszy i M kolumn. Następnie usunięto dwa ostatnie kafelki z ostatniego wiersza i pomieszano całe ułożenie. Mieszanie polegało na wielokrotnym przesuwaniu kafelka w pionie lub poziomie na sąsiednie wolne pole. Celem gracza jest podać kolejność ruchów, po których wykonaniu otrzyma pierwotny obrazek.
Jasiowi udało się już ustalić, na które miejsce będzie musiał trafić każdy z kafelków. Każdemu kafelkowi nadał numer zgodny z pozycją, na które ma trafić. Są to liczby od 1 do N ⋅ M − 2, a pozycje numerowane są kolejno wierszami od góry do dołu, a wewnątrz wiersza od lewej do prawej.
Poniższy rysunek obrazuje jedną z sekwencji, która prowadzi do ułożenia obrazka z testu przykładowego:
Niestety Jasio nie potrafi znaleźć takiej sekwencji ruchów. Pomóż mu i napisz program, który znajdzie takie ruchy.
Wejście
Pierwszy wiersz wejścia zawiera dwie liczby całkowite N i M. Kolejne N wierszy zawiera po M liczb całkowitych, gdzie j-ta liczba w i-tym wierszu oznacza numer xij – wartość wpisaną na kafelku w i-tym wierszu i j-tej kolumnie obrazka. Liczba 0 pojawia się dokładnie dwa razy i oznacza pusty kafelek. Każda z pozostałych liczb reprezentujących wartości na kafelkach pojawi się na wejściu dokładnie raz.
Wyjście
W pierwszym wierszu wyjścia wypisz jedną liczbę R, oznaczającą liczbę ruchów, które planujesz wykonać. W~każdym z kolejnych R wierszy wypisz dwie liczby ki, di oznaczające numer kafelka oraz kierunek, w którym należy go przesunąć. Kierunek to cyfra od 0 do 3 oznaczająca przesunięcia kolejno w: górę, prawo, dół, lewo. Twoja odpowiedź zostanie zaakceptowana jeżeli nie będzie dłuższa niż 100 000 kroków, każdy ruch będzie poprawnie zdefiniowany, a po ostatnim ruchu plansza będzie poprawnie ułożona.
Ograniczenia
3 ≤ N, M ≤ 8, 0 ≤ xij ≤ N ⋅ M − 2.
Przykłady
| Wejście | Wyjście | |
|
|