Problem description

Na planszy N × N z polami ponumerowanymi z góry na dół, od lewej do prawej należy znaleźć zygzak przechodzący od pola numer A do pola numer B. Zygzak powinien przejść przez wszystkie pola planszy, a w każdym momencie możliwe jest przemieszczenie do dowolnego pola sąsiadującego bokiem z bieżącym polem głowy zygzaka:

Napisz program, który: wczyta opis planszy, pole startowe i końcowe, wyznaczy wszystkie możliwe zygzaki i wypisze wyniki na standardowe wyjście.

Wejście

W pierwszym (jedynym) wierszu wejścia znajdują się trzy liczby naturalne N, A oraz B, pooddzielane pojedynczymi odstępami. Są to kolejno: długość boku planszy oraz numery pól: startowego i końcowego.

Wyjście

Program powinien wypisać rozwiązania zagadki w osobnych wierszach w kolejności leksykograficznej w postaci ciągu znaków G (góra), D (dół), L (lewo), P (prawo).

Ograniczenia

2 ≤ N ≤ 7, 1 ≤ A, B ≤ N², A ≠ B.

Przykład

3 3 7

DDLGGLDD
LLDPPDLL