You are given an H × W grid.
The squares in the grid are described by H strings, S_1,...,S_H.
The j-th character in the string S_i corresponds to the square at the i-th row from the top and j-th column from the left (1 \leq i \leq H,1 \leq j \leq W).
`.` stands for an empty square, and `#` stands for a square containing a bomb.

Dolphin is interested in how many bomb squares are horizontally, vertically or diagonally adjacent to each empty square.
(Below, we will simply say "adjacent" for this meaning. For each square, there are at most eight adjacent squares.)
He decides to replace each `.` in our H strings with a digit that represents the number of bomb squares adjacent to the corresponding empty square.

Print the strings after the process.

Constraints

* 1 \leq H,W \leq 50
* S_i is a string of length W consisting of `#` and `.`.

Input

Input is given from Standard Input in the following format:


H W
S_1
:
S_H


Output

Print the H strings after the process.
The i-th line should contain a string T_i of length W, where the j-th character in T_i corresponds to the square at the i-th row from the top and j-th row from the left in the grid (1 \leq i \leq H, 1 \leq j \leq W).

Examples

Input

3 5
.....
.#.#.
.....


Output

11211
1#2#1
11211


Input

3 5


Output




Input

6 6
.
.#.##
.#
.#..#.
.##..
.#...


Output

3
8#7##
5#
4#65#2
5##21
4#310
#include <bits/stdc++.h>
using namespace std;

int main() {
        int H, W;
        cin >> H >> W;
        char s[H][W];
        int t[H][W] = {};

        for (int i = 0; i < H; i++) {
                for (int j = 0; j < W; j++) {
                        cin >> s[i][j];
                }
        }

        for (int i = 0; i < H; i++) {
                for (int j = 0; j < W; j++) {
                        if (i == 0) { // 最上段
                                if (j == 0) { // 左端
                                        if (s[i][j + 1] == '#') { // 右
                                                t[0][0]++;
                                        }
                                        if (s[i + 1][j] == '#') { // 下
                                                t[0][0]++;
                                        }
                                        if (s[i + 1][j + 1] == '#') { // 右下
                                                t[0][0]++;
                                        }
                                }
                                if (0 < j && j < (W - 1)) { // 端以外
                                        if (s[i][j - 1] == '#') { // 左
                                                t[0][j]++;
                                        }
                                        if (s[i][j + 1] == '#') { // 右
                                                t[0][j]++;
                                        }
                                        if (s[i + 1][j] == '#') { // 下
                                                t[0][j]++;
                                        }
                                        if (s[i + 1][j - 1] == '#') { // 左下
                                                t[0][j]++;
                                        }
                                        if (s[i + 1][j + 1] == '#') { // 右下
                                                t[0][j]++;
                                        }
                                }
                                if (j == (W - 1)) { // 右端
                                        if (s[i][j - 1] == '#') { // 左
                                                t[0][W - 1]++;
                                        }
                                        if (s[i + 1][j] == '#') { // 下
                                                t[0][W - 1]++;
                                        }
                                        if (s[i + 1][j - 1] == '#') { // 左下
                                                t[0][W - 1]++;
                                        }
                                }
                        }
                        if (0 < i && i < (H - 1)) { // 最上段と最下段以外
                                if (j == 0) { // 左端
                                        if (s[i - 1][j] == '#') { // 上
                                                t[i][0]++;
                                        }
                                        if (s[i][j + 1] == '#') { // 右
                                                t[i][0]++;
                                        }
                                        if (s[i + 1][j] == '#') { // 下
                                                t[i][0]++;
                                        }
                                        if (s[i - 1][j + 1] == '#') { // 右上
                                                t[i][0]++;
                                        }
                                        if (s[i + 1][j + 1] == '#') { // 右下
                                                t[i][0]++;
                                        }
                                }
                                if (0 < j && j < (W - 1)) { // 端以外
                                        if (s[i - 1][j] == '#') { // 上
                                                t[i][j]++;
                                        }
                                        if (s[i][j + 1] == '#') { // 右
                                                t[i][j]++;
                                        }
                                        if (s[i + 1][j] == '#') { // 下
                                                t[i][j]++;
                                        }
                                        if (s[i][j - 1] == '#') { // 左
                                                t[i][j]++;
                                        }
                                        if (s[i - 1][j - 1] == '#') { // 左上
                                                t[i][j]++;
                                        }
                                        if (s[i - 1][j + 1] == '#') { // 右上
                                                t[i][j]++;
                                        }
                                        if (s[i + 1][j - 1] == '#') { // 左下
                                                t[i][j]++;
                                        }
                                        if (s[i + 1][j + 1] == '#') { // 右下
                                                t[i][j]++;
                                        }
                                }
                                if (j == (W - 1)) { // 右端
                                        if (s[i - 1][W - 1] == '#') { // 上
                                                t[i][W - 1]++;
                                        }
                                        if (s[i][W - 2] == '#') { // 左
                                                t[i][W - 1]++;
                                        }
                                        if (s[i + 1][W - 1] == '#') { // 下
                                                t[i][W - 1]++;
                                        }
                                        if (s[i - 1][W - 2] == '#') { // 左上
                                                t[i][W - 1]++;
                                        }
                                        if (s[i + 1][W - 2] == '#') { // 左下
                                                t[i][W - 1]++;
                                        }
                                }
                        }
                        if (i == (H - 1)) { // 最下段
                                if (j == 0) { // 左端
                                        if (s[H - 2][j] == '#') { // 上
                                                t[H - 1][j]++;
                                        }
                                        if (s[H - 1][j + 1] == '#') { // 右
                                                t[H - 1][j]++;
                                        }
                                        if (s[H - 2][j + 1] == '#') { // 右上
                                                t[H - 1][j]++;
                                        }
                                }
                                if (0 < j && j < (W - 1)) { // 端以外
                                        if (s[H - 1][j - 1] == '#') { // 左
                                                t[H - 1][j]++;
                                        }
                                        if (s[H - 2][j] == '#') { // 上
                                                t[H - 1][j]++;
                                        }
                                        if (s[H - 1][j + 1] == '#') { // 右
                                                t[H - 1][j]++;
                                        }
                                        if (s[H - 2][j - 1] == '#') { // 左上
                                                t[H - 1][j]++;
                                        }
                                        if (s[H - 2][j + 1] == '#') { // 右上
                                                t[H - 1][j]++;
                                        }
                                }
                                if (j == (W - 1)) { // 右端
                                        if (s[H - 2][W - 1] == '#') { // 上
                                                t[H - 1][W - 1]++;
                                        }
                                        if (s[H - 1][W - 2] == '#') { // 左
                                                t[H - 1][W - 1]++;
                                        }
                                        if (s[H - 2][W - 2] == '#') { // 左上
                                                t[H - 1][W - 1]++;
                                        }
                                }
                        }
                }
        }
        for (int i = 0; i < H; i++) {
                for (int j = 0; j < W; j++) {
                        if (s[i][j] == '#') {
                            cout << s[i][j];
                        } else {
                            cout << t[i][j];
                        }
                }
                cout << endl;
        }
}
