N Puzzle is a sliding blocks game that takes place on a k * k grid with ((k * k) - 1) tiles each numbered from 1 to N. Your task is to reposition the tiles to their proper order.

Input Format

The first line of the input contains an integer k, the size of the square grid. k * k lines follow each line containing an integer I on the tile starting from the top left to bottom right. The empty cell is represented by the number 0.

N = (k * k) -1
0 <= I <= N

Constraints

3 <= k <= 5

Output Format

The first line contains an integer, M, the number of moves your algorithm has taken to solve the N-Puzzle. M lines follow. Each line indicating the movement of the empty cell (0).

A grid is considered solved if it is of the following configuration.

0 1 2
3 4 5
6 7 8

Sample Input

3
0
3
8
4
1
7
2
6
5

Sample Output

70
RIGHT
DOWN
...
...
...

Explanation

The board given as input is

0 3 8
4 1 7
2 6 5

After RIGHT, the board's configuration is

3 0 8
4 1 7
2 6 5

Task

Print all the moves made from the given configuration to the final solved board configuration.

Scoring

On successfully solving the puzzle, your score will be k * k.

  1. Challenge Walkthrough
    Let's walk through this sample challenge and explore the features of the code editor.1 of 6
  2. Review the problem statement
    Each challenge has a problem statement that includes sample inputs and outputs. Some challenges include additional information to help you out.2 of 6
  3. Choose a language
    Select the language you wish to use to solve this challenge.3 of 6
  4. Enter your code
    Code your solution in our custom editor or code in your own environment and upload your solution as a file.4 of 6
  5. Test your code
    You can compile your code and test it for errors and accuracy before submitting.5 of 6
  6. Submit to see results
    When you're ready, submit your solution! Remember, you can go back and refine your code anytime.6 of 6
  1. Check your score