Minesweeper

Interview

Time limit2sMemory limit1024 MB

Summary

Given a black and white grid, build a minesweeper map where white cells are empty and black cells hold a mine or a number from 1 to 8, or report that none exists.

Level: Medium4 of 10
Topics: Implementation, Greedy
Solved: No attempts yet

Statement

Vasya likes the game Minesweeper. The game is played by one person on a grid with $m$ rows and $n$ columns. Some cells contain mines. Every other cell either contains a number from 1 to 8, which is the count of mines in the cells that share at least one corner with it, or is empty, which means no adjacent cell has a mine. A cell holds at most one mine. A grid with mines and numbers is called a map.

Vasya wants to draw his own maps from black and white pictures. Each picture is drawn on squared paper, and some cells are colored black while the others stay white. For each picture, he needs a map that follows this rule: a black cell must contain either a mine or a number from 1 to 8, and a white cell must be empty.

Write a program that builds such a map for Vasya.

Input

The first line contains two integers $m$ and $n$ ( $1 \le m, n \le 100$ ), the number of rows and columns. The next $m$ lines each contain $n$ numbers separated by spaces. Each number is 0 or 1. A 0 means the cell is white, and a 1 means the cell is black.

Output

Print the map as $m$ lines of $n$ characters each, with no spaces between characters. Print * for a cell with a mine, the digit for a cell with a number, and . for an empty cell.

If no map matches the picture, print a single line with No solution.

Examples2

Example 1

Input

Expected output

.1*1
1211
*1..

Example 2
Input
```
3 3
0 1 0
1 0 1
0 1 0
```
Expected output
```
No solution
```