Hi codeforces. Please help me. How to solve this problem acmp.ru

Horse riding

It is required to make a round of a rectangular field, moving in it according to the rules of a chess horse. In the labyrinth there are cells that can not be moved. The initial position of the horse is determined. It is necessary to visit all cells (in which the transition is possible) without repeated calls. It is guaranteed that such a bypass exists.

Input

The first line of the input file INPUT.TXT contains two natural numbers N and M — the field sizes (N, M ≤ 100). Next, the map of the field follows: N lines of M characters in each line. The symbol "." (Dot) denotes an empty space. The symbol "X" indicates that movement to this cell is prohibited. The initial position of the knight is given by the unique "K" in the field.

Output

In the output file OUTPUT.TXT output the bypass matrix of the field, in each cell of which the step number of its visit must be entered (starting with one). Cells labeled "X" in the input data should be labeled with a zero value when outputting. Numbers should be separated by spaces, it is allowed to use extra spaces. In the case of an ambiguous solution, you should deduce any.