Lines of Containers

A shipment of logs, the main export of Nlogonia, sits in the harbour cargo terminal, packed in containers. All containers are cubes of the same size. The terminal holds them in $L$ lines and $C$ columns, so there are $LC$ containers in total. Each container carries a distinct identification number from $1$ to $LC$.

Each of the $L$ lines is loaded onto a different ship. To keep unloading simple in each destination country, the numbers along a line must increase from left to right. The first line must hold containers $1$ through $C$ in increasing order, the second line must hold containers $C+1$ through $2C$ in increasing order, and so on until the last line, which holds containers $(L-1)C+1$ through $LC$. Figure (a) shows the correct arrangement of a shipment with 5 lines and 4 columns.

A crane swaps two whole lines, or two whole columns. It cannot move any other group of containers, and it cannot move a single container.

On the night before loading, the workers ran the cranes and swapped lines and columns to protest their low salaries. Figure (b) shows the arrangement after lines 1 and 4 were swapped. Figure (c) shows the arrangement after one further swap, this time between columns 2 and 3.

Loading has to happen today, so the containers must first be returned to the arrangement described above. Given the position of every container after the protest, write a program that decides whether the cranes alone can put every container back where it belongs. If they can, also compute the smallest possible total number of line swaps and column swaps.

The first line of input contains two integers $L$ and $C$, the number of lines and the number of columns of the shipment. Each of the next $L$ lines describes the arrangement after the protest and contains $C$ integers $X_{l,1}, X_{l,2}, \dots, X_{l,C}$, where $X_{l,c}$ is the number of the container standing in line $l$ and column $c$. Every integer from $1$ to $LC$ appears exactly once.

Constraints

• $1 \le L \le 300$
• $1 \le C \le 300$
• $1 \le X_{l,c} \le LC$

Print a single line with the minimum total number of line swaps and column swaps needed to put every container back in its original position. If the cranes alone cannot do it, that line must contain only the character *.