Franco continues to learn robotics and is very happy because he built his second robot. His original plan was for this robot to be able to play Hopscotch, but since this is very difficult, he settles for a simpler version of this game.
On the floor, there is a board drawn with $$$N \times M$$$ squares. Let $$$(i,j)$$$ be the square located in row $$$i$$$ and column $$$j$$$. Due to the heavy rain lately, some of these squares are wet.
The robot can start its journey from any point outside the board and can only move horizontally and vertically, that is, in the directions parallel to the edges of the board. The robot can walk on both dry and wet squares. However, to change its direction of movement from vertical to horizontal (or vice versa), the robot must be inside a dry square. The robot can change its direction at most once in each square, but it can pass through it as many times as it wants. It can never change its direction by $$$180^\circ$$$. The journey must end outside the board.
For the journey to be valid, the robot must have changed its direction in all the dry squares. Below is a valid journey on a $$$3\times 3$$$ board, where the squares containing a circle are wet squares and the others are dry squares:
The goal is to determine a valid journey if it exists, for which each dry square must be assigned a distinct integer between $$$1$$$ and $$$s$$$ (where $$$s$$$ is the number of dry squares), so that the numbers indicate the order of the $$$s$$$ direction changes that the robot will make on the dry squares.
A line with two integers $$$N$$$ and $$$M$$$ $$$(1 \leq N, M \leq 1000)$$$, representing the number of rows and columns of the board.
Then, the $$$i$$$-th of the following $$$N$$$ lines contains $$$M$$$ characters separated by a space. Each of these is "." or "0". If the character in position $$$j$$$ is ".", then the square $$$(i,j)$$$ is dry, and if it is "0", it is wet.
It is guaranteed that there is at least one dry square.
If there is no valid journey, a single line containing "*".
Otherwise, $$$N$$$ lines that describe the board with the numbers written in the dry squares.
Formally, the $$$i$$$-th of the $$$N$$$ lines must contain $$$M$$$ integers. The $$$j$$$-th of them must be "0" if the square $$$(i,j)$$$ was wet, and an integer between $$$1$$$ and $$$s$$$ if that square was dry, as described in the statement.
If there are multiple valid journeys, any of them will be accepted.
3 3 . 0 0 0 . . . 0 .
1 0 0 0 5 4 2 0 3
3 2 0 . 0 0 . .
0 3 0 0 1 2
1 3 . . .
*
