Background

NOIP2015 Junior Group T2

Problem Description

Minesweeper is a classic single-player game. In an $n$ by $m$ grid, some squares contain mines (referred to as mine squares), while others do not (referred to as non-mine squares). When a player uncovers a non-mine square, it displays a number indicating how many of its surrounding squares contain mines. The goal of the game is to uncover all non-mine squares without uncovering any mine squares.

Given the mine distribution in an $n$ by $m$ grid, the task is to calculate the number of mine squares surrounding each non-mine square.

Note: A square's surrounding squares include those directly adjacent in the eight directions: up, down, left, right, upper-left, upper-right, lower-left, and lower-right.

Input Format

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

The following $n$ lines, each containing $m$ characters, describe the mine distribution in the minefield. The character * denotes a mine square, and the character ? denotes a non-mine square. There are no separators between adjacent characters.

Output Format

The output file should contain $n$ lines, each with $m$ characters, describing the entire minefield. Use * to denote mine squares and the number of surrounding mines to denote non-mine squares. There are no separators between adjacent characters.

Sample Input and Output

Input Sample #1

3 3
*??
???
?*?

Output Sample #1

*10
221
1*1

Input Sample #2

2 3
?*?
*??

Output Sample #2

2*1
*21

Notes

For $100\%$ of the data, $1 \leq n \leq 100, 1 \leq m \leq 100$.

见题面 Input 部分

见题面 Output 部分