Problem E
Moonfrost Canyon

Karin has three favourite things in life – fine dining, cats and a video game called Moonfrost Canyon. In the game, you play as a farmer who got tired of city life to move out to a farm together with your cat. At the farm, you then grow crops that you can cook fancy meals out of.

When growing crops, you plant seeds at various locations in the $R \times C$ grid that your farm consists of. In total, you have an infinite amount of seeds for four different kinds of plants.

Karin has tilled some squares on her farm, on which seeds can be planted. When planting seeds, you take 9 seeds for the same kind of plant and place them in a tilled $3 \times 3$ grid that does not already contain any seeds.

Finally, to avoid potential crop disease from spreading, no two patches of seeds in the grid that shares an edge may have a seed of the same crop placed in it. Otherwise, this could allow a disease affecting one $3 \times 3$ patch of crops to spread to the patch it shares an edge with.

Given the size of Karin’s in-game farm and what squares are tilled, can you help her determine what seeds to place where in order to plant a seed on every tilled square subject to these constraints?

Input

The first line of input contains the two integers $1 \le R, C \le 1\, 000$, the height and width of Karin’s farm.

The next $R$ lines each contains $C$ characters describing Karin’s farm. Each character is either a . which denotes a tilled square, or a * which denotes a non-tilled square.

The input will always be such that it is possible to construct a seed plan as described.

Output

Output $R$ lines, each containing $C$ characters describing how Karin should plant her crops. If a square was non-tilled, output a *. Otherwise, output a digit 1-4 depending on which of the four kinds of seeds was planted on the square.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. To get the points for a test group you need to solve all test cases in the test group. Your final score will be the maximum score of a single submission.

5 5
*****
*...*
*...*
*...*
*****

*****
*111*
*111*
*111*
*****

6 7
...*...
...*...
...*...
**...**
**...**
**...**

111*111
111*111
111*111
**222**
**222**
**222**