Description

Little H is very keen on the $N^2$ puzzle game on his mobile phone in his spare time.

Little H plays the standard $N^2$ puzzle game, which consists of $N^2-1$ sliding tiles and one empty space arranged in an $N \times N$ rectangle. The goal is to move the empty space up, down, left, or right to arrange the $N^2-1$ tiles into a specific order.

Finally, before his calculus final exam, Little H set his game record to a terrifying height.

Little H believes that within the limits of human intelligence, it is almost an impossible task to continue improving his score. He therefore thought of asking an expert to help him write a program. Of course, Little H hopes that the resulting sequence of moves is as short as possible, so that he can press them faster!

Input

This is a submission-based problem. All input files puzzle1~10.in are already in the corresponding directory.

The first line of the input file puzzle*.in contains a positive integer $N$, representing the size of the game Little H wants you to solve.

The next $N$ lines each contain $N$ integers $A_{i, j}$ between $0$ and $N^2-1$, representing the tile number in the $i$-th row and $j$-th column. Specifically, $A_{i, j}=0$ indicates that the cell is an empty space. All $A_{i, j}$ are distinct.

Output

The output file puzzle*.out consists of 2 lines. The first line contains an integer $L$, representing the length of the answer you provide. The second line is a string $S$ of length $L$, where $S_i$ is one of 'D', 'U', 'R', 'L', representing that you move the tile above, below, left, or right into the empty space at the $i$-th step, such that the final tiles are arranged as:

$$ \begin{matrix} 1 & 2 & \dots & N-1 & N \\ N+1 & N+2 & \dots & 2N-1 & 2N \\ \dots & \dots & \dots & \dots & \dots \\ N^2-N+1 & N^2-N+2 & \dots & N^2-1 & \text{empty} \end{matrix} $$

Examples

Input 1

3
1 2 3
4 8 5
7 0 6

Output 1

9
LDRULDRUL

Interaction

We provide a tool called puzzle_check to test whether your output file is acceptable. The usage of this tool is to enter the following in the command line:

puzzle_check input_filename output_filename s

When $s='1'$, puzzle_check will output your movement steps for analysis. When $s \neq '1'$, it will not output the steps.

For example: puzzle_check puzzle2.in puzzle2.out 1 means testing whether your puzzle2.out is valid with respect to the input puzzle2.in, and outputting the movement steps.

After calling this program, puzzle_check will provide the test results based on your output file, including:

• Illegal exit: Unknown error;
• "Unable to seek file: XX.": Cannot find the test file;
• "Mismatch in string length.": The $L$ given in the output file does not match the actual length;
• "Error while moving on step k.": An error occurred during the $k$-th move. (You can use the step output to check.)
• "Incorrect result.": The final result does not meet the requirements.
• "Correct! Total movement: k.": The output is correct, and the number of moves $k$ will be used for scoring.

Note: 1. puzzle_check does not check for errors in the input. Therefore, please ensure the correctness of the input. 2. If there is any disagreement or inconsistency with the actual result of puzzle_check during the competition, please raise it in time to avoid unnecessary errors that may affect your final score.

Subtasks

Each test case is scored individually.

For each test case, if your output file is invalid (e.g., incorrect file format, solution does not meet requirements, etc.), such that puzzle_check does not return a correct feedback, the test case receives 0 points.

Otherwise, if the number of moves in your output is your_ans, and the best result obtained by all contestants in the competition along with the best answer provided by the judges is best_ans, we also set a parameter $d$ for scoring. Your score for this test case is as follows:

If your_ans $\ge$ best_ans $+ d$, you get 2 points.

Otherwise, the score is: $$\left\lfloor \left( \frac{\text{best\_ans} + d - \text{your\_ans}}{d} \right)^{\frac{3}{2}} \times 8 \right\rfloor + 2$$

In general cases, you can assume $d \approx \text{best\_ans} \times 0.75$.

Implementation Details

To make it easier for contestants to get started with the game (and to pass the extra time), we provide a simple simulation tool EMU. Its usage is to enter the following in the command line:

EMU filename1 filename2

The simulation tool will read the game from filename1 (an input file) and display the game state in the terminal. Contestants can use 'i', 'k', 'j', 'l' to move the empty space up, down, left, and right. When the contestant enters the character 'e', the simulation tool prints the movement process to filename2 and exits.

Note

The problem may be more complex than you imagine. Please analyze the algorithm complexity carefully before starting.

Please keep the input file puzzle*.in and your output puzzle*.out safe and back them up in time to avoid accidental deletion.