You are given a rectangular field of n × m cells. Each cell is either empty or impassable (contains an obstacle). Empty cells are marked with '.', impassable cells are marked with '*'. Let's call two empty cells adjacent if they share a side.

Let's call a connected component any non-extendible set of cells such that any two of them are connected by the path of adjacent cells. It is a typical well-known definition of a connected component.

For each impassable cell (x, y) imagine that it is an empty cell (all other cells remain unchanged) and find the size (the number of cells) of the connected component which contains (x, y). You should do it for each impassable cell independently.

The answer should be printed as a matrix with n rows and m columns. The j-th symbol of the i-th row should be "." if the cell is empty at the start. Otherwise the j-th symbol of the i-th row should contain the only digit —- the answer modulo 10. The matrix should be printed without any spaces.

To make your output faster it is recommended to build the output as an array of n strings having length m and print it as a sequence of lines. It will be much faster than writing character-by-character.

As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.


-----Input-----

The first line contains two integers n, m (1 ≤ n, m ≤ 1000) — the number of rows and columns in the field.

Each of the next n lines contains m symbols: "." for empty cells, "*" for impassable cells.


-----Output-----

Print the answer as a matrix as described above. See the examples to precise the format of the output.


-----Examples-----
Input
3 3
*.*
.*.
*.*

Output
3.3
.5.
3.3

Input
4 5
**..*
..***
.*.*.
*.*.*

Output
46..3
..732
.6.4.
5.4.3



-----Note-----

In first example, if we imagine that the central cell is empty then it will be included to component of size 5 (cross). If any of the corner cell will be empty then it will be included to component of size 3 (corner).

Difficulty: interview

Starter code:

Solutions:
"""
	Author		: Arif Ahmad
	Date  		: 
	Algo  		: 
	Difficulty	: 
"""
from sys import stdin, stdout
from collections import deque

g = None # contains the actual graph
h = None # h[x][y] represents the component in which cell (x,y) belongs
r = None
c = None
visited = None
total = None
comp = None
dx = [-1, 0, 0, 1]
dy = [0, -1, 1, 0]


def bfs(x, y):
	nonlocal total
	
	q = deque([(x, y)])
	total += 1
	visited[x][y] = True
	h[x][y] = comp
	while q:
		x, y = q.pop()
		#print('comp:', comp, 'cell:', x, y)
		for k in range(4):
			#print('loop:', k)
			nx = x + dx[k]
			ny = y + dy[k]
			#print(visited)
			#print('new cell:', nx, ny, 'check:', nx>=0 , nx<r , ny>=0 , ny<c , visited[nx][ny]==False , g[nx][ny]=='.')
			if nx>=0 and nx<r and ny>=0 and ny<c and visited[nx][ny]==False and g[nx][ny]=='.':
				q.appendleft((nx, ny))
				total += 1
				visited[nx][ny] = True
				h[nx][ny] = comp


def main():
	nonlocal g, h, r, c, visited, comp, total

	r, c = [int(_) for _ in stdin.readline().split()]

	g = []
	for i in range(r):
		line = stdin.readline()
		g.append(list(line))

	component = []
	h = [[-1 for i in range(c)] for j in range(r)]
	visited = [[False for i in range(c)] for j in range(r)]
	#print(visited)

	for i in range(r):
		for j in range(c):
			if visited[i][j] == False and g[i][j] == '.':
				comp = len(component)
				total = 0
				#print('calling bfs', i, j)
				bfs(i, j)
				component.append(total)

	for x in range(r):
		for y in range(c):
			if g[x][y] == '*':
				ans = 0
				idx = set()
				for k in range(4):
					nx = x + dx[k]
					ny = y + dy[k]
					if nx>=0 and nx<r and ny>=0 and ny<c and g[nx][ny]=='.':
						idx.add(h[nx][ny])
				for item in idx:
					#print(component[item])
					ans += component[item]
				ans += 1
				ans %= 10
				g[x][y] = str(ans)

	#print(component)
	for i in range(r):
		stdout.write(''.join(g[i]))

	

def __starting_point():
    main()

__starting_point()

# n=int(input())
# n,k=map(int,input().split())
# arr=list(map(int,input().split()))
#ls=list(map(int,input().split()))
#for i in range(m):
# for _ in range(int(input())):
from collections import Counter
#from fractions import Fraction
#n=int(input())
#arr=list(map(int,input().split()))
#ls = [list(map(int, input().split())) for i in range(n)]
from math import log2
#for _ in range(int(input())):
#n, m = map(int, input().split())
# for _ in range(int(input())):
from math import gcd
#n=int(input())
# for i in range(m):
# for i in range(int(input())):
# n,k= map(int, input().split())
# arr=list(map(int,input().split()))
# n=sys.stdin.readline()
# n=int(n)
# n,k= map(int, input().split())
# arr=list(map(int,input().split()))
# n=int(inaput())
#for _ in range(int(input())):
#arr=list(map(int,input().split()))
from collections import  deque
dx=[-1,0,0,1]
dy=[0,-1,1,0]

def bfs(x,y):
	nonlocal total
	total+=1
	q=deque([(x,y)])
	v[x][y]=True
	h[x][y]=comp
	#q.append()
	while q:
		x,y=q.pop()
		for i in range(4):
			nx=x+dx[i]
			ny=y+dy[i]
			#print("nx,y",nx, ny)
			if (nx>=0 and nx<n) and (ny>=0 and ny<m) and (v[nx][ny]==False) and (g[nx][ny]=="."):
				q.appendleft((nx,ny))
				total+=1
				v[nx][ny]=True
				h[nx][ny]=comp

#nonlocal g,h,r,comp,total
n, m = list(map(int, input().split()))
h=[[-1 for i in range(m)] for j in range(n)]
g=[]
v=[[False for i in range(m)]for j in range(n)]
for i in range(n):
	g.append(list(input()))
component=[]
for i in range(n):
	for j in range(m):
		if v[i][j]==False and g[i][j]==".":############
			comp=len(component)
			#nonlocal total
			total=0
			bfs(i,j)
			component.append(total)
#print(component)
for x in range(n):
	for y in range(m):
		if g[x][y] == "*":
			ans = 0
			s = set()
			for k in range(4):
				nx = x + dx[k]
				ny = y + dy[k]
				if nx >= 0 and nx < n and ny >= 0 and ny < m and g[nx][ny] == ".":
					s.add(h[nx][ny])
			for itm in s:
				ans += component[itm]
			ans += 1
			ans %= 10
			g[x][y] = str(ans)
for i in range(n):
	print("".join(g[i]))

























import sys
input = sys.stdin.readline

n, m = list(map(int, input().split()))

class DisjointSetUnion:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.num_sets = n

    def find(self, a):
        acopy = a
        while a != self.parent[a]:
            a = self.parent[a]
        while acopy != a:
            self.parent[acopy], acopy = a, self.parent[acopy]
        return a

    def union(self, a, b):
        a, b = self.find(a), self.find(b)
        if a != b:
            if self.size[a] < self.size[b]:
                a, b = b, a

            self.num_sets -= 1
            self.parent[b] = a
            self.size[a] += self.size[b]

    def set_size(self, a):
        return self.size[self.find(a)]

    def __len__(self):
        return self.num_sets


l = []
for i in range(n):
    l.append(input().strip())

UF = DisjointSetUnion(n * m)
for i in range(n):
    for j in range(m):
        if i < n - 1:
            if l[i][j] == '.' and l[i+1][j] == '.':
                UF.union(m * i + j, m * i + m + j)
        if j < m - 1:
            if l[i][j] == '.' and l[i][j+1] =='.':
                UF.union(m * i + j, m * i + j + 1)

out = []
for i in range(n):
    curr = []
    for j in range(m):
        if l[i][j] == '.':
            curr.append('.')
        else:
            dx = [0,0,-1,1]
            dy = [-1,1,0,0]
            adj = set()
            for d in range(4):
                nx = i + dx[d]
                ny = j + dy[d]
                if 0 <= nx < n and 0 <= ny < m and l[nx][ny] == '.':
                    adj.add(UF.find(m * nx + ny))
                    
            outV = 1
            for v in adj:
                outV += UF.set_size(v)
            curr.append(str(outV % 10))
    out.append(''.join(curr))
print('\n'.join(out))
                
    


from sys  import stdin,stdout

st=lambda:list(stdin.readline().strip())
li=lambda:list(map(int,stdin.readline().split()))
mp=lambda:list(map(int,stdin.readline().split()))
inp=lambda:int(stdin.readline())
pr=lambda n: stdout.write(str(n)+"\n")

def valid(x,y):
    if x>=n or y>=m or x<0 or y<0:
        return False
    if v[x][y] or l[x][y]=='*':
        return False
    return True

dx=[-1,1,0,0]
dy=[0,0,1,-1]

def DFS(i,j,val):
    ans=1
    connected=[(i,j)]
    stack=[(i,j)]
    v[i][j]=True
    while stack:
        a,b=stack.pop()
        for x in range(4):
            newX,newY=a+dx[x], b+dy[x]
            if valid(newX,newY):
                stack.append((newX,newY))
                v[newX][newY]=True
                connected.append((newX,newY))
                ans= (ans%10 + 1%10) % 10
                
    for i in connected:
        a,b=i
        l[a][b]=(ans,val)
    
        
    
n,m=mp()
l=[st() for i in range(n)]
val=0
k=[list(i) for i in l]
v=[[False for i in range(m)] for j in range(n)]
for i in range(n):
    for j in range(m):
        if l[i][j]=='.' and not v[i][j]:
            DFS(i,j,val)
            val+=1

for  i in range(n):
    for j in range(m):
        if l[i][j]=='*':
            k[i][j]=1
            s=set()
            for x in range(4):
                newX,newY= i+dx[x], j+dy[x]
                if newX>=0 and newY>=0 and newX<n and newY<m:
                    if type(l[newX][newY])==tuple:
                        A,B=l[newX][newY]
                        if B not in s:
                            k[i][j]+=A
                            k[i][j]%=10
                            s.add(B)
                
            
print('\n'.join([''.join([str(i) for i in j]) for j in k]))
            
                        
                
            


from sys  import stdin,stdout

st=lambda:list(stdin.readline().strip())
li=lambda:list(map(int,stdin.readline().split()))
mp=lambda:list(map(int,stdin.readline().split()))
inp=lambda:int(stdin.readline())
pr=lambda n: stdout.write(str(n)+"\n")

def valid(x,y):
    if x>=n or y>=m or x<0 or y<0:
        return False
    if v[x][y] or l[x][y]=='*':
        return False
    return True

dx=[-1,1,0,0]
dy=[0,0,1,-1]

def DFS(i,j,val):
    ans=1
    connected=[(i,j)]
    stack=[(i,j)]
    v[i][j]=True
    while stack:
        a,b=stack.pop()
        for x in range(4):
            newX,newY=a+dx[x], b+dy[x]
            if valid(newX,newY):
                stack.append((newX,newY))
                v[newX][newY]=True
                connected.append((newX,newY))
                ans= ans+1
                
    for i in connected:
        a,b=i
        l[a][b]=(ans,val)
    
        
    
n,m=mp()
l=[st() for i in range(n)]
val=0
k=[list(i) for i in l]
v=[[False for i in range(m)] for j in range(n)]
for i in range(n):
    for j in range(m):
        if l[i][j]=='.' and not v[i][j]:
            DFS(i,j,val)
            val+=1

for  i in range(n):
    for j in range(m):
        if l[i][j]=='*':
            k[i][j]=1
            s=set()
            for x in range(4):
                newX,newY= i+dx[x], j+dy[x]
                if newX>=0 and newY>=0 and newX<n and newY<m:
                    if type(l[newX][newY])==tuple:
                        A,B=l[newX][newY]
                        if B not in s:
                            k[i][j]+=A
                            k[i][j]%=10
                            s.add(B)
                
            
print('\n'.join([''.join([str(i) for i in j]) for j in k]))
            
                        
                
            


from sys  import stdin,stdout

st=lambda:list(stdin.readline().strip())
li=lambda:list(map(int,stdin.readline().split()))
mp=lambda:list(map(int,stdin.readline().split()))
inp=lambda:int(stdin.readline())
pr=lambda n: stdout.write(str(n)+"\n")

def valid(x,y):
    if x>=n or y>=m or x<0 or y<0:
        return False
    if v[x][y] or l[x][y]=='*':
        return False
    return True

dx=[-1,1,0,0]
dy=[0,0,1,-1]

def DFS(i,j,val):
    ans=1
    connected=[(i,j)]
    stack=[(i,j)]
    v[i][j]=True
    while stack:
        a,b=stack.pop()
        for x in range(4):
            newX,newY=a+dx[x], b+dy[x]
            if valid(newX,newY):
                stack.append((newX,newY))
                v[newX][newY]=True
                connected.append((newX,newY))
                ans= ans+1
                
    for i in connected:
        a,b=i
        l[a][b]=(ans,val)
    
        
    
n,m=mp()
l=[st() for i in range(n)]
val=0
k=[list(i) for i in l]
v=[[False for i in range(m)] for j in range(n)]
for i in range(n):
    for j in range(m):
        if l[i][j]=='.' and not v[i][j]:
            DFS(i,j,val)
            val+=1

for  i in range(n):
    for j in range(m):
        if l[i][j]=='*':
            k[i][j]=1
            s=set()
            for x in range(4):
                newX,newY= i+dx[x], j+dy[x]
                if newX>=0 and newY>=0 and newX<n and newY<m:
                    if len(l[newX][newY])==2:
                        A,B=l[newX][newY]
                        if B not in s:
                            k[i][j]+=A
                            k[i][j]%=10
                            s.add(B)
                
            
print('\n'.join([''.join([str(i) for i in j]) for j in k]))
            
                        
                
            


from sys  import stdin,stdout

st=lambda:list(stdin.readline().strip())
li=lambda:list(map(int,stdin.readline().split()))
mp=lambda:list(map(int,stdin.readline().split()))
inp=lambda:int(stdin.readline())
pr=lambda n: stdout.write(str(n)+"\n")

def valid(x,y):
    if x>=n or y>=m or x<0 or y<0:
        return False
    if v[x][y] or l[x][y]=='*':
        return False
    return True

dx=[-1,1,0,0]
dy=[0,0,1,-1]

def DFS(i,j,val):
    ans=1
    connected=[(i,j)]
    stack=[(i,j)]
    v[i][j]=True
    while stack:
        a,b=stack.pop()
        for x in range(4):
            newX,newY=a+dx[x], b+dy[x]
            if valid(newX,newY):
                stack.append((newX,newY))
                v[newX][newY]=True
                connected.append((newX,newY))
                ans= ans+1
                
    for i in connected:
        a,b=i
        l[a][b]=(ans,val)
    
        
    
n,m=mp()
l=[st() for i in range(n)]
val=0
k=[list(i) for i in l]
v=[[False for i in range(m)] for j in range(n)]
for i in range(n):
    for j in range(m):
        if l[i][j]=='.' and not v[i][j]:
            DFS(i,j,val)
            val+=1

for  i in range(n):
    for j in range(m):
        if l[i][j]=='*':
            k[i][j]=1
            s=set()
            for x in range(4):
                newX,newY= i+dx[x], j+dy[x]
                if newX>=0 and newY>=0 and newX<n and newY<m:
                    if type(l[newX][newY])==tuple:
                        A,B=l[newX][newY]
                        if B not in s:
                            k[i][j]+=A
                            k[i][j]%=10
                            s.add(B)
                
            
print('\n'.join([''.join([str(i) for i in j]) for j in k]))
            



from sys  import stdin,stdout

st=lambda:list(stdin.readline().strip())
li=lambda:list(map(int,stdin.readline().split()))
mp=lambda:list(map(int,stdin.readline().split()))
inp=lambda:int(stdin.readline())
pr=lambda n: stdout.write(str(n)+"\n")

def valid(x,y):
    if x>=n or y>=m or x<0 or y<0:
        return False
    if v[x][y] or l[x][y]=='*':
        return False
    return True

dx=[-1,1,0,0]
dy=[0,0,1,-1]

def DFS(i,j,val):
    ans=1
    connected=[(i,j)]
    stack=[(i,j)]
    v[i][j]=True
    while stack:
        a,b=stack.pop()
        for x in range(4):
            newX,newY=a+dx[x], b+dy[x]
            if valid(newX,newY):
                stack.append((newX,newY))
                v[newX][newY]=True
                connected.append((newX,newY))
                ans= ans+1
                
    for i in connected:
        a,b=i
        l[a][b]=(ans,val)
    
        
    
n,m=mp()
l=[st() for i in range(n)]
val=0
k=[list(i) for i in l]
v=[[False for i in range(m)] for j in range(n)]
for i in range(n):
    for j in range(m):
        if l[i][j]=='.' and not v[i][j]:
            DFS(i,j,val)
            val+=1

for  i in range(n):
    for j in range(m):
        if l[i][j]=='*':
            k[i][j]=1
            s=set()
            for x in range(4):
                newX,newY= i+dx[x], j+dy[x]
                if 0<=newX<n and 0<=newY<m:
                    if type(l[newX][newY])==tuple:
                        A,B=l[newX][newY]
                        if B not in s:
                            k[i][j]+=A
                            k[i][j]%=10
                            s.add(B)
                
            
print('\n'.join([''.join([str(i) for i in j]) for j in k]))