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).
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;

import java.util.*;

public class A_GENERAL {
   
	// for fast output printing  : use printwriter or stringbuilder
	// remember to close pw using pw.close()
	static StringBuilder sb = new StringBuilder();
	static long seive_size = (long) 1e6;
	static String alpha = "abcdefghijklmnopqrstuvwxyz";
    static ArrayList<Integer> primes = new ArrayList<>();
    static boolean[] set = new boolean[(int) seive_size+1];
    static int n, m, k;
    static ArrayList<Integer>[] adj;
    static boolean[] vis;
    static ArrayDeque<Integer> q = new ArrayDeque<>();
    static final long MOD = 998244353;
    static int[] dx = new int[] {1, 0, -1, 0, 1, 1, -1, -1};
    static int[] dy = new int[] {0, 1, 0, -1, 1, -1, 1, -1};
    static long[][] arr;
    static int[] rank;
    static int[] parent;

    static char[][] s;
    static boolean[][] mark;
    static int c = 1;
    static int[][] id;
    static int[] val;
    static int count = 0;
    public static void main(String[] args) {
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		MyScanner sc = new MyScanner();
		n = sc.nextInt();
		m = sc.nextInt();
		s = new char[n][m];
		for(int i = 0; i < n; i++) {
			s[i] = sc.next().toCharArray();
		}
		mark = new boolean[n][m];
		id = new int[n][m];
		val = new int[n*m+1];
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				if(!mark[i][j] && s[i][j] == '.') {
					count = 0;
					dfs(i, j);
					val[c] = count;
					c++;
				}
			}
		}
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < m; j++) {
				if(s[i][j] == '*') {
					HashSet<Integer> set = new HashSet<>();
					f(i, j-1, set);
					f(i, j+1, set);
					f(i+1, j, set);
					f(i-1, j, set);
					int tot = 1;
					for(int x : set) {
						tot += val[x];
					}
					tot %= 10;
					s[i][j] = (tot+"").charAt(0);
				}
				
				out.print(s[i][j]);
			}
			out.println();
		}
		out.close();
	}
    public static void f(int i, int j, HashSet<Integer> set) {
    	if(i < 0 || j < 0 || i > n-1 || j > m-1 || s[i][j] == '*') {
    		return;
    	}
    	set.add(id[i][j]);
    }
    public static void dfs(int i, int j) {
    	if(i < 0 || j < 0 || i > n-1 || j > m-1 || mark[i][j] || s[i][j] == '*') {
    		return;
    	}
    	count++;
    	id[i][j] = c;
    	mark[i][j] = true;
    	dfs(i+1, j);
    	dfs(i-1, j);
    	dfs(i, j+1);
    	dfs(i, j-1);
    }
    
	public static class Triplet implements Comparable<Triplet> {
		int x;
    	int y;
    	int z;
    	Triplet(int x, int y, int z) {
    		this.x = x;
    		this.y = y;
    		this.z = z;
    	}
    	public int compareTo(Triplet o) {
    		return Integer.compare(this.x, o.x);
    	}
    }
	public static class Pair implements Comparable<Pair>{
		long f;
		long s;
		Pair(long f, long s) {
			this.f = f;
			this.s = s;
		}
		public int compareTo(Pair o) {
			return Long.compare(this.f, o.f);
		}
	}
	public static void init(int n) {
    	adj = new ArrayList[n+1];
    	vis = new boolean[n+1];
    	parent = new int[n+1];
		rank = new int[n+1];
    	for(int i = 0; i <= n; i++) {
    		adj[i] = new ArrayList();
    		parent[i] = i;
			rank[i] = 0;
    	}
    }
	// print string "s" multiple times 
	// prefer to use this function for multiple printing
	public static String mp(String s, int times) {
		return String.valueOf(new char[times]).replace("\0", s);
	}
	// take log with base 2
 	public static long log2(long k) {
 		return 63-Long.numberOfLeadingZeros(k);
 	}

 	// using lambda function for sorting
   	public static void lambdaSort() {
   		Arrays.sort(arr, (a, b) -> Double.compare(a[0], b[0]));
   	}
  	
  	// (n choose k) = (n/k) * ((n-1) choose (k-1))
  	public static long choose(long n, long k) {
 		return (k == 0) ? 1 : (n*choose(n-1, k-1))/k;
 	}

 	// just for keeping gcd function for other personal purposes
 	public static long gcd(long a, long b) {
 		return (a == 0) ? b : gcd(b%a, a);
 	}
 	
	public static long max(long... as) {
        long max = Long.MIN_VALUE;
        for (long a : as) max = Math.max(a, max);
        return max;
    }

    public static long min(int... as) {
        long min = Long.MAX_VALUE;
        for (long a : as) min = Math.min(a, min);
        return min;
    }
 	
    public static long modpow(long x, long n, long mod) {
    	if(n == 0) return 1%mod;
    	long u = modpow(x, n/2, mod);
    	u = (u*u)%mod;
    	if(n%2 == 1) u = (u*x)%mod;
    	return u;
    }
 	// ======================= binary search (lower and upper bound) =======================
	public static int lowerBound(long[] a, int x) {
		int lo = 0;
 		int hi = a.length-1;
 		int ans = -1;
 		while(lo <= hi) {
 			int mid = (lo+hi)/2;
 			if(x < a[mid]) {
 				hi = mid-1;
 			} else if(x > a[mid]) {
 				lo = mid+1;
 			} else if(lo != hi) {
 				 hi = mid-1; 		// for first occurrence
 				 ans = mid;
 			} else {
 				return mid;
 			}
 		}
 		return ans;
	}
	
	public static int upperBound(long[] a, long x) {
		int lo = 0;
		int hi = a.length-1;
		int ans = -1;
		while(lo <= hi) {
			int mid = (lo+hi)/2;
			if(x < a[mid]) {
				hi = mid-1;
			} else if(x > a[mid]) {
				lo = mid+1;
			} else if(lo != hi) {
				lo = mid+1;			// for last occurrence
				ans = mid;
			} else {
				return mid;
			}
		}
		return ans;
	}
	// ================================================================

	// ================== SEIVE OF ERATOSTHENES =======================
	// Complexity : O(N * log(log(N)))       ( almost O(N) )
	public static void generatePrimes() {
		// set.add(0);
		// set.add(1);
		Arrays.fill(set, true);
		set[0] = false;
		set[1] = false;
		for(int i = 2; i <= seive_size; i++) {
			if(set[i]) {
				for(long j = (long) i*i; j <= seive_size; j+=i) 
					set[(int)j] = false;
				primes.add(i);
			}
		}
	}
  
	public static boolean isPrime(long N) {
		if(N <= seive_size) return set[(int)N];
		for (int i = 0; i < (int)primes.size(); i++)
			if (N % primes.get(i) == 0) return false;
		return true;
	}
	// ===========================================================
  
 	// ================ Permutation of String ====================
 	public static void permute(String str) {
 		permute(str, 0, str.length()-1);
 	}
 	public static void permute(String str, int l, int r) 
    { 
        if (l == r) 
            System.out.println(str); 
        else
        { 
            for (int i = l; i <= r; i++) 
            { 
                str = swap(str,l,i); 
                permute(str, l+1, r); 
                str = swap(str,l,i); 
            } 
        } 
    }
	public static String swap(String a, int i, int j) 
    { 
        char temp; 
        char[] charArray = a.toCharArray(); 
        temp = charArray[i] ; 
        charArray[i] = charArray[j]; 
        charArray[j] = temp; 
        return String.valueOf(charArray); 
    } 
	// Union-find
	// static int[] parent, rank;
//	public static void makeSet(int n) {
//
//		parent = new int[n+1];
//		rank = new int[n+1];
//		for(int i = 1; i <= n; i++) {
//			parent[i] = i;
//			rank[i] = 0;
//		}
//	}
	public static int find(int u) {

		if(parent[u] == u)	return u;

		int v = find(parent[u]);
		parent[u] = v;
		return v;

	}
	public static boolean connected(int u, int v) {
		return find(u) == find(v);
	}
	public static void Union(int u, int v) {

		int x = find(u);				//root of u
		int y = find(v);				//root of v

		if(x == y)		return;
		if(rank[x] == rank[y]) {
			parent[y] = x;
			rank[x]++;
		}
		else if(rank[x] > rank[y]) {
			parent[y] = x;
		}
		else {
			parent[x] = y;
		}

	}
	
//	public static int dijkstra(int x, int y) {
//    	int[] dist = new int[n+1];
//    	Arrays.fill(dist, Integer.MAX_VALUE);
//    	PriorityQueue<Node> q = new PriorityQueue<>();
//    	q.add(new Node(x, 0));
//    	dist[x] = 0;
//    	while(!q.isEmpty()) {
//    		Node node = q.poll();
//    		int u = node.key;
//    		if(u == y) {
//    			break;
//    		}
//    		for(int v : res[u]) {
//    			if(dist[v] > dist[u]+count[u]) {
//    				dist[v] = dist[u] + count[u];
//    				q.add(new Node(v, dist[v]));
//    			}
//    		}
//    	}
//    	if(dist[y] == Integer.MAX_VALUE) {
//    		return -1;
//    	}
//    	return dist[y];
//    }
	
	public static class MyScanner {
		BufferedReader br;
		StringTokenizer st;
		public MyScanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {while (st == null || !st.hasMoreElements()) {
			try {st = new StringTokenizer(br.readLine());}
			catch (IOException e) {e.printStackTrace();}}
		return st.nextToken();}
		int nextInt() {return Integer.parseInt(next());}
		long nextLong() {return Long.parseLong(next());}
		double nextDouble() {return Double.parseDouble(next());}
		String nextLine(){String str = "";
		try {str = br.readLine();}
		catch (IOException e) {e.printStackTrace();}
		return str;}
		int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        int[] nextIntArray(int n, int delta) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt() + delta;
            return a;
        }

        long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }
	}

}