Description

Minesweeper is a classic single-player mini game. In an $n$-row by $m$-column minefield, some cells contain mines (called mine cells), and the other cells do not (called non-mine cells). When the player reveals a non-mine cell, the cell shows a number indicating how many of its neighboring cells are mine cells. The goal is to find all non-mine cells without revealing any mine cell.

Given the distribution of mines in an $n$-row by $m$-column minefield, compute for every non-mine cell the number of neighboring mine cells.

Note: The neighboring cells of a cell include the eight directly adjacent cells in the up, down, left, right, upper-left, upper-right, lower-left, and lower-right directions.

Input Format

The first line contains two integers $n$ and $m$ separated by a space, representing the number of rows and columns of the minefield, respectively.

Then follow $n$ lines, each with $m$ characters, describing the distribution of mines in the minefield. The character $\texttt{*}$ indicates a mine cell, and the character $\texttt{?}$ indicates a non-mine cell. There are no delimiters between adjacent characters.

Output Format

The output contains $n$ lines, each with $m$ characters, describing the entire minefield. Use $\texttt{*}$ for mine cells, and use the number of neighboring mines for non-mine cells. There are no delimiters between adjacent characters.

3 3
*??
???
?*?

*10
221
1*1

2 3
?*?
*??

2*1
*21

Hint

For $100\%$ of the testdata, $1 \le n \le 100$, $1 \le m \le 100$.

Translated by ChatGPT 5