ajax ... nettuts

Problem

Consider a generalized 15-puzzle (Fifteen Puzzle) with NxN square grids.

Given a random initial position of the grid, you have to write a program to slide the tile numbered "1" to the first position (i.e. the top-left corner).

Input:

Output: Print the configuration of the puzzle after each step till the tile numbered "1" moves to the top. The empty slot can be depicted by the character "x"

Example

Input:

3 << note: indicates a 3x3 square, i.e. an 8-puzzle)
345
286
71x
Output:

345
286
71x

345
28x
716

345
2x8
716

345
218
7x6

345
218
x76

345
x18
276

345
1x8
276

3x5
148
276

x35
148
276

135
x48
276