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: MEDIUM_HARD
Tags: Graph traversal

Starter code:

Solutions:
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
(n, m) = map(int, stdin.readline().split())
mtx = [[ch for ch in stdin.readline()] for _ in range(n)]
groups = [[0 for _ in range(m)] for _ in range(n)]
sizes = [0]
shard_id = 1
for i in range(n):
	for j in range(m):
		if mtx[i][j] == '*':
			continue
		if groups[i][j] != 0:
			continue
		stack = [(i, j)]
		size = 1
		groups[i][j] = shard_id
		while stack:
			(x, y) = stack.pop()
			for (xi, yi) in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
				if xi < 0 or n <= xi:
					continue
				if yi < 0 or m <= yi:
					continue
				if mtx[xi][yi] != '.':
					continue
				if groups[xi][yi] != 0:
					continue
				groups[xi][yi] = shard_id
				stack.append((xi, yi))
				size += 1
		sizes.append(size)
		shard_id += 1
for i in range(n):
	for j in range(m):
		if mtx[i][j] != '*':
			continue
		groups_id = set()
		for (xi, yi) in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
			if xi < 0 or n <= xi:
				continue
			if yi < 0 or m <= yi:
				continue
			if mtx[xi][yi] != '.':
				continue
			groups_id.add(groups[xi][yi])
		size = 1
		for gid in groups_id:
			size += sizes[gid]
		mtx[i][j] = str(size)[-1]
stdout.write('\n'.join((''.join(row) for row in mtx)))


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]))


import sys
(n, m) = map(int, sys.stdin.buffer.readline().decode('utf-8').split())
a = [list(line.decode('utf-8').rstrip()) for line in sys.stdin.buffer]
group = [[0] * m for _ in range(n)]
size = [0]
gi = 1
for i in range(n):
	for j in range(m):
		if a[i][j] == '*' or group[i][j] != 0:
			continue
		stack = [(i, j)]
		cnt = 1
		group[i][j] = gi
		while stack:
			(y, x) = stack.pop()
			for (ty, tx) in ((y + 1, x), (y - 1, x), (y, x + 1), (y, x - 1)):
				if 0 <= ty < n and 0 <= tx < m and (a[ty][tx] == '.') and (group[ty][tx] == 0):
					group[ty][tx] = gi
					stack.append((ty, tx))
					cnt += 1
		size.append(cnt)
		gi += 1
for i in range(n):
	for j in range(m):
		if a[i][j] != '*':
			continue
		adj = set()
		for (ty, tx) in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
			if 0 <= ty < n and 0 <= tx < m and (a[ty][tx] == '.'):
				adj.add(group[ty][tx])
		res = 1
		for g in adj:
			res += size[g]
		a[i][j] = str(res)[-1]
sys.stdout.buffer.write('\n'.join((''.join(row) for row in a)).encode('utf-8'))


from collections import defaultdict
import sys
input = sys.stdin.readline

def get_root(s):
	v = []
	while not s == root[s]:
		v.append(s)
		s = root[s]
	for i in v:
		root[i] = s
	return s

def unite(s, t):
	root_s = get_root(s)
	root_t = get_root(t)
	if not root_s == root_t:
		if rank[s] == rank[t]:
			root[root_t] = root_s
			rank[root_s] += 1
			size[root_s] += size[root_t]
		elif rank[s] > rank[t]:
			root[root_t] = root_s
			size[root_s] += size[root_t]
		else:
			root[root_s] = root_t
			size[root_t] += size[root_s]

def same(s, t):
	if get_root(s) == get_root(t):
		return True
	else:
		return False
(n, m) = map(int, input().split())
l = n * m
root = [i for i in range(l)]
rank = [1 for _ in range(l)]
size = [1 for _ in range(l)]
s = []
for i in range(n):
	s0 = list(input().rstrip())
	for j in range(m - 1):
		if s0[j] == s0[j + 1] == '.':
			unite(m * i + j, m * i + j + 1)
	s.append(s0)
for i in range(n - 1):
	for j in range(m):
		if s[i][j] == s[i + 1][j] == '.':
			if not same(m * i + j, m * (i + 1) + j):
				unite(m * i + j, m * (i + 1) + j)
cnt = defaultdict(lambda : 0)
r = [0] * l
for i in range(l):
	x = get_root(i)
	r[i] = x
	cnt[x] += 1
v = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for i in range(n):
	for j in range(m):
		if not s[i][j] == '*':
			continue
		s0 = set()
		for (di, dj) in v:
			(ni, nj) = (i + di, j + dj)
			if 0 <= ni < n and 0 <= nj < m:
				if s[ni][nj] == '.':
					s0.add(r[m * ni + nj])
		ans = 1
		for k in s0:
			ans += cnt[k]
		s[i][j] = str(ans % 10)
for s0 in s:
	print(''.join(s0))


import sys
input = sys.stdin.readline
from collections import defaultdict

class UnionFind:

	def __init__(self, n):
		self.table = [-1] * n

	def root(self, x):
		stack = []
		tbl = self.table
		while tbl[x] >= 0:
			stack.append(x)
			x = tbl[x]
		for y in stack:
			tbl[y] = x
		return x

	def find(self, x, y):
		return self.root(x) == self.root(y)

	def unite(self, x, y):
		r1 = self.root(x)
		r2 = self.root(y)
		if r1 == r2:
			return
		d1 = self.table[r1]
		d2 = self.table[r2]
		if d1 <= d2:
			self.table[r2] = r1
			self.table[r1] += d2
		else:
			self.table[r1] = r2
			self.table[r2] += d1

	def get_size(self, x):
		return -self.table[self.root(x)]
(n, m) = map(int, input().split())
a = [list(input().rstrip()) for i in range(n)]
uf = UnionFind(n * m)
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
for i in range(n):
	for j in range(m):
		if a[i][j] == '.':
			for k in range(4):
				ni = i + dy[k]
				nj = j + dx[k]
				if 0 <= ni < n and 0 <= nj < m and (a[ni][nj] == '.'):
					uf.unite(m * i + j, m * ni + nj)
ans = [[''] * m for i in range(n)]
for i in range(n):
	for j in range(m):
		if a[i][j] == '.':
			ans[i][j] = '.'
		else:
			tmp = 0
			use = []
			for k in range(4):
				(ni, nj) = (i + dy[k], j + dx[k])
				if 0 <= ni < n and 0 <= nj < m and (a[ni][nj] == '.'):
					flag = True
					for val in use:
						if uf.find(val, m * ni + nj):
							flag = False
					if flag:
						use.append(m * ni + nj)
						tmp += uf.get_size(m * ni + nj)
			ans[i][j] = str((tmp + 1) % 10)
for i in range(n):
	print(''.join(ans[i]))


from collections import deque
dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]
componentsizes = {}
componentid = 0
(n, m) = map(int, input().split())
field = [list(input()) for _ in range(n)]

def valid(y, x):
	return y >= 0 and x >= 0 and (y < n) and (x < m)

def component(y, x):
	size = 1
	q = deque([(y, x)])
	field[y][x] = componentid
	while q:
		(y, x) = q.pop()
		for (i, j) in dirs:
			if valid(y + i, x + j) and field[y + i][x + j] == '.':
				q.appendleft((y + i, x + j))
				field[y + i][x + j] = componentid
				size += 1
	return size

def solve(y, x):
	connected = set()
	for (i, j) in dirs:
		if valid(y + i, x + j) and type(field[y + i][x + j]) is int:
			connected.add(field[y + i][x + j])
	return (sum((componentsizes[i] for i in connected)) + 1) % 10
for i in range(n):
	for j in range(m):
		if field[i][j] == '.':
			componentsizes[componentid] = component(i, j)
			componentid += 1
output = [[] for _ in range(n)]
for i in range(n):
	for j in range(m):
		output[i].append(str(solve(i, j)) if field[i][j] == '*' else '.')
print('\n'.join([''.join(row) for row in output]))


from sys import stdin, stdout
from collections import deque
g = None
h = None
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()
		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 (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)]
	for i in range(r):
		for j in range(c):
			if visited[i][j] == False and g[i][j] == '.':
				comp = len(component)
				total = 0
				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:
					ans += component[item]
				ans += 1
				ans %= 10
				g[x][y] = str(ans)
	for i in range(r):
		stdout.write(''.join(g[i]))

def __starting_point():
	main()
__starting_point()


from collections import Counter
from math import log2
from math import gcd
from collections import deque
dx = [-1, 0, 0, 1]
dy = [0, -1, 1, 0]

def bfs(x, y):
	global total
	total += 1
	q = deque([(x, y)])
	v[x][y] = True
	h[x][y] = comp
	while q:
		(x, y) = q.pop()
		for i in range(4):
			nx = x + dx[i]
			ny = y + dy[i]
			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
(n, m) = 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)
			total = 0
			bfs(i, j)
			component.append(total)
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]))


from functools import cmp_to_key
from collections import deque, Counter
from heapq import heappush, heappop
from math import log, ceil
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def ii():
	return int(inp())

def si():
	return str(inp())

def li(lag=0):
	l = list(map(int, inp().split()))
	if lag != 0:
		for i in range(len(l)):
			l[i] += lag
	return l

def mi(lag=0):
	matrix = list()
	for i in range(n):
		matrix.append(li(lag))
	return matrix

def lsi():
	return list(map(str, inp().split()))

def print_list(lista, space=' '):
	print(space.join(map(str, lista)))

def bisect_left(a, x):
	left = 0
	right = len(a)
	while left < right:
		mid = (left + right) // 2
		if a[mid] < x:
			left = mid + 1
		else:
			right = mid
	return left

def bisect_right(a, x):
	left = 0
	right = len(a)
	while left < right:
		mid = (left + right) // 2
		if a[mid] > x:
			right = mid
		else:
			left = mid + 1
	return left

def bisect_elements(a, x):
	return bisect_right(a, x) - bisect_left(a, x)
MOD = 10 ** 9 + 7
maxN = 5
FACT = [0] * maxN
INV_FACT = [0] * maxN

def add(x, y):
	return (x + y) % MOD

def multiply(x, y):
	return x * y % MOD

def power(x, y):
	if y == 0:
		return 1
	elif y % 2:
		return multiply(x, power(x, y - 1))
	else:
		a = power(x, y // 2)
		return multiply(a, a)

def inverse(x):
	return power(x, MOD - 2)

def divide(x, y):
	return multiply(x, inverse(y))

def allFactorials():
	FACT[0] = 1
	for i in range(1, maxN):
		FACT[i] = multiply(i, FACT[i - 1])

def inverseFactorials():
	n = len(INV_FACT)
	INV_FACT[n - 1] = inverse(FACT[n - 1])
	for i in range(n - 2, -1, -1):
		INV_FACT[i] = multiply(INV_FACT[i + 1], i + 1)

def coeffBinom(n, k):
	if n < k:
		return 0
	return multiply(FACT[n], multiply(INV_FACT[k], INV_FACT[n - k]))

def create_graph(n, m, undirected=1, unweighted=1):
	graph = [[] for i in range(n)]
	if unweighted:
		for i in range(m):
			[x, y] = li(lag=-1)
			graph[x].append(y)
			if undirected:
				graph[y].append(x)
	else:
		for i in range(m):
			[x, y, w] = li(lag=-1)
			w += 1
			graph[x].append([y, w])
			if undirected:
				graph[y].append([x, w])
	return graph

def create_tree(n, unweighted=1):
	children = [[] for i in range(n)]
	if unweighted:
		for i in range(n - 1):
			[x, y] = li(lag=-1)
			children[x].append(y)
			children[y].append(x)
	else:
		for i in range(n - 1):
			[x, y, w] = li(lag=-1)
			w += 1
			children[x].append([y, w])
			children[y].append([x, w])
	return children

def dist(tree, n, A, B=-1):
	s = [[A, 0]]
	(massimo, massimo_nodo) = (0, 0)
	distanza = -1
	v = [-1] * n
	while s:
		(el, dis) = s.pop()
		if dis > massimo:
			massimo = dis
			massimo_nodo = el
		if el == B:
			distanza = dis
		for child in tree[el]:
			if v[child] == -1:
				v[child] = 1
				s.append([child, dis + 1])
	return (massimo, massimo_nodo, distanza)

def diameter(tree):
	(_, foglia, _) = dist(tree, n, 0)
	(diam, _, _) = dist(tree, n, foglia)
	return diam

def dfs(graph, n, A):
	v = [-1] * n
	s = [[A, 0]]
	v[A] = 0
	while s:
		(el, dis) = s.pop()
		for child in graph[el]:
			if v[child] == -1:
				v[child] = dis + 1
				s.append([child, dis + 1])
	return v

def bfs(graph, n, A):
	v = [-1] * n
	s = deque()
	s.append([A, 0])
	v[A] = 0
	while s:
		(el, dis) = s.popleft()
		for child in graph[el]:
			if v[child] == -1:
				v[child] = dis + 1
				s.append([child, dis + 1])
	return v

def parents_children_root_unrooted_tree(tree, n, root=0):
	q = deque()
	visited = [0] * n
	parent = [-1] * n
	children = [[] for i in range(n)]
	q.append(root)
	while q:
		all_done = 1
		visited[q[0]] = 1
		for child in tree[q[0]]:
			if not visited[child]:
				all_done = 0
				q.appendleft(child)
		if all_done:
			for child in tree[q[0]]:
				if parent[child] == -1:
					parent[q[0]] = child
					children[child].append(q[0])
			q.popleft()
	return (parent, children)

def all_longest_path_passing_from_node(parent, children, n):
	q = deque()
	visited = [len(children[i]) for i in range(n)]
	downwards = [[0, 0] for i in range(n)]
	upward = [1] * n
	longest_path = [1] * n
	for i in range(n):
		if not visited[i]:
			q.append(i)
			downwards[i] = [1, 0]
	while q:
		node = q.popleft()
		if parent[node] != -1:
			visited[parent[node]] -= 1
			if not visited[parent[node]]:
				q.append(parent[node])
		else:
			root = node
		for child in children[node]:
			downwards[node] = sorted([downwards[node][0], downwards[node][1], downwards[child][0] + 1], reverse=True)[0:2]
	s = [node]
	while s:
		node = s.pop()
		if parent[node] != -1:
			if downwards[parent[node]][0] == downwards[node][0] + 1:
				upward[node] = 1 + max(upward[parent[node]], downwards[parent[node]][1])
			else:
				upward[node] = 1 + max(upward[parent[node]], downwards[parent[node]][0])
		longest_path[node] = downwards[node][0] + downwards[node][1] + upward[node] - min([downwards[node][0], downwards[node][1], upward[node]]) - 1
		for child in children[node]:
			s.append(child)
	return longest_path

def check(i, j, n, m):
	return i > -1 and j > -1 and (i < n) and (j < m)

def dfs_len(tab, i, j):
	d = [-1, 0, 1, 0, -1]
	n = len(tab)
	m = len(tab[0])
	stack = list()
	stack.append([i, j])
	visti[i][j] = 1
	count = 0
	while stack:
		(a, b) = stack.pop()
		count += 1
		for k in range(4):
			x = a + d[k]
			y = b + d[k + 1]
			if check(x, y, n, m) and tab[x][y] == '.' and (visti[x][y] == 0):
				visti[x][y] = 1
				par[x][y] = i * m + j
				stack.append([x, y])
	return count
(n, m) = li()
tab = list()
for i in range(n):
	tab.append(si())
visti = [[0 for i in range(m)] for j in range(n)]
par = [[-1 for i in range(m)] for j in range(n)]
le = [[0 for i in range(m)] for j in range(n)]
for i in range(n):
	for j in range(m):
		if tab[i][j] == '.' and visti[i][j] == 0:
			par[i][j] = i * m + j
			count = dfs_len(tab, i, j)
			le[i][j] = count
d = [-1, 0, 1, 0, -1]
res = [['.' for i in range(m)] for j in range(n)]
for i in range(n):
	for j in range(m):
		if tab[i][j] != '.':
			count = 1
			parenti = list()
			for k in range(4):
				x = i + d[k]
				y = j + d[k + 1]
				if check(x, y, n, m):
					p = par[x][y]
					if p not in parenti:
						parenti.append(p)
			for p in parenti:
				if p != -1:
					yj = p % m
					xi = p // m
					count += le[xi][yj]
			res[i][j] = count % 10
for i in range(n):
	print_list(res[i], '')