Description
In addition to the eight queen puzzle, another famous puzzle that has also been generalized is the fifteen puzzle. For a puzzle of size n × n, natural numbers below n2 are placed into squares leaving one empty. The puzzle is solved by sliding the squares until it looks similar to that shown in the figure below. Given the starting configuration, you are to find a solution or report that no solution exists.
Input
The input contains exactly one test case. The first line of input contains n (n ≤ 10). The next n2 numbers describe the puzzle by rows. The empty square is represented by zero.
Output
If no solution exists, just print “No Answer!”. Otherwise print a string consisting of the letters “L” (left), “R” (right), “U” (up), “D” (down) showing how the empty square moves to solve the puzzle.
Sample Input
2
3 1
2 0
Sample Output
LURD
