Quiz
Almost everyone of you knows children's game "barley-break". At this problem you have to find a solution for some position.
The game includes square fi eld N×N, divided into cells 1×1. There are checks in each cells except of one. Number from 1 to N^2-1. is written on each cell. Each number occurs only once. At one turn you may move one of the chiecks next to the empty cell to it. Cell, where the check was, becomes empty. Checks cannot leave field.
Solving puzzle means placing checks in the speci c order:
Empty place must be in the last cell of the last line.
For usual barley-break it looks so:
Position is given, nd sequence of turns (not necessarily shortest, probably empty) which solves it. Or output, that position has no solution.
Input
The first line contains number N, that is size of the field. It is followed by N lines with N numbers in each. Numbers from 1 to N^2-1 correspond to checks, 0 corresponds to empty place. Each number from 0 to N^2-1 occurs only once.
Output
If position has no solution, write "No". Else write "Yes", in the fi rst line and appropriate sequence of turns, written in second line without spaces. Turns are encoded by next way:
'L' - means, that check to the left of the empty place must be moved to it.
'R' - means, that check to the right of the empty place must be moved to it.
'U' - means, that check above the empty place must be moved to it.
'D' - means, that check below the empty place must be moved to it.
Turns number must not exceed 2500000. You may display any solutions if there are multiple ones.
Limits
2 ≤ N ≤ 50
0 ≤ a_ij ≤ N^2-1