AlgoLiga 2018

Piętnastka to bardzo popularna układanka z którą na pewno wielu z Was się już spotkało. Jest ona skonstruowana z 15 przesuwających się kwadratowych elementów, z których każdy ma numer od 1 do 15. Wszystkie elementy są umieszczone w ramce o wymiarach 4 na 4, jedno pole tej ramki jest puste. W układance należy tak poprzesuwać jej elementy, aby otrzymać porządek pokazany na obrazku obok:

Jedynym dozwolonym ruchem jest zamiana brakującego elementu z jednym z 2, 3 bądź 4 elementów, z którymi ma on wspólną krawędź. Oznaczamy ruchy za pomocą kierunku, w którym "przesunęło" się puste pole. Dozwolonymi wartościami są: "R", "L", "U" oraz "D" oznaczające kolejno ruch pustego pola w prawo, lewo, do góry i na dół.

Dla początkowej konfiguracji układanki musisz określić ciąg ruchów, który doprowadzi Cię do stanu końcowego. W testach każdy rozwiązywalny układ początkowy piętnastki wymaga co najwyżej 50 ruchów i tyle też maksymalnie możesz wykonać.

Wejście

Wejście składa się z opisu konfiguracji początkowej piętnastki. Cztery wiersze po cztery liczby każdy opisujące kolejne rzędy układanki. Zero oznacza brakujący element. Na wejściu nie występuje konfiguracja końcowa piętnastki.

Wyjście

Jeżeli dla danej konfiguracji początkowej nie ma rozwiązania wypisz jedno słowo "NIE".  Jeżeli układankę można ułożyć, wypisz w sposób opisany wyżej dowolny ciąg ruchów wykonujących to.

Przykład 1

Wejście:
2 3 4 0
1 5 7 8
9 6 10 12
13 14 11 15

Przykładowe wyjście:
LLLDRDRDR

Przykład 2

Wejście:
13 1 2 4
5 0 3 7
9 6 10 12
15 8 11 14

Wyjście:
NIE