Sorting the puzzle P27048

Statement

thehtml

Consider a puzzle consisting of a board n × m, where all the squares except one have a different number between 1 and n*m − 1 . The only allowed movement consists of moving an adjacent number (horizontally or vertically) to the empty square, it makes that the empty square “moves” where the number was. The aim is to leave the puzzle sorted from top to bottom and from left to right, with the empty square at the bottom on the left.

Write a program that prints if a given puzzle has solution or not. If it has, your program must print which is the minimal number of steps to solve it.

Input

Input consists of two natural numbers strictly positive (and small) n and m, followed by n rows with m natural numbers each one. Each number between 0 and n*m − 1 appears exactly once; the zero indicates the square initially empty.

Output

Your program must print the minimal number of steps to solve the puzzle, following the format of the instances. If there is not any possible solution, it must print "no solution".

Public test cases

Input

3 5
 1  2  3  4  5
 6  7  8  9 10
11 12 13 14  0

Output

has solution in 0 steps

Input

1 6
1 2 3 4 0 5

Output

has solution in 1 steps

Input

2 3
1 0 5
4 3 2

Output

has solution in 6 steps

Input

2 2
1 3
2 0

Output

no solution

Input

Output

has solution in 16 steps

Information

Author: Salvador Roura
Language: English
Translator: Carlos Molina
Original language: Catalan
Other languages: Catalan
Official solutions: C++
User solutions