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).
//pakage joney_000[let_me_start]
 
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;
/*
 * Author    : joney_000[let_me_start]
 * Algorithm : Not Specified
 * Platform  : CodeForces
 */
 
 /*                The Main Class                */
public class C
{   
    public static InputStream inputStream = System.in;
    public static OutputStream outputStream = System.out;
    public static FastReader in = new FastReader(inputStream);;
    public static PrintWriter out = new PrintWriter(outputStream);;
    /*
    Overhead [Additional Temporary Strorage]
    */
    public static int tempints[] = new int[100005];
    public static long templongs[] = new long[100005];
    public static double tempdoubles[] = new double[100005];
    public static char tempchars[] = new char[100005];
    public static long mod = 1000000000+7;
    static int n = 0 , m = 0  ,si = 0 , sj = 0 , maxl = 0;
    static int dx[] = {-1 ,  0 , 0, 1 };
    static int dy[] = { 0 , -1 , 1, 0};
    static ArrayList[] adj = null;
    static boolean v[][]  ,  mat[][];
    static int arr[][] = new int[1005][1005];
    static int t[][] = new int[1005][1005];
    static int id = 0;
        public static void main(String[] args) throws java.lang.Exception{
        //let_me_start 
    /*  BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out=new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br=new BufferedReader(new FileReader("input.txt"));
        BufferedWriter out=new BufferedWriter(new FileWriter("output.txt"));
3
5 5
....*
...*.
..*..
...*.
....*
2 2
*.
..
3 3
.*.
***
.*.    
    
    
    
    */ 
    
    //  int tests = i();
        mat = new boolean[1004][1004];
        v = new boolean[1004][1004];
        //int vis[] = new int[1001 * 1001 + 1]; 
    //  for(int  t =1; t<= tests ;t++){
        
         n = i();  m = i();
         
         for(int i=1;i<=n;i++){
            String s = s();
            for(int j = 1 ; j<= m ; j++){
                if(s.charAt(j-1)=='*'){
                    mat[i][j] = true;
                
                }
                //  adj[idx(i,j)] = new ArrayList();
                //  vis[idx(i,j)] = false;
            }
            
         }
    
         for(int i=1;i<=n;i++){
            for(int j = 1 ; j<= m ; j++){
                v[i][j] = false;
            }
         }  
         id = 1;
         for(int i=1;i<=n;i++){
            for(int j = 1 ; j<= m ; j++){
                if((!mat[i][j])&&(!v[i][j])){bfs(i, j);id++;}
            }
         }   
        // out.write(""+ans+"\n");
         out.flush();
    //  }
         for(int i=1;i<=n;i++){
            for(int j = 1 ; j<= m ; j++){
                if((!mat[i][j]))out.write(".");
                else out.write(""+(1+arr[i][j])%10);
            }
            out.write("\n");
         }
        out.flush();
        return;
        }    
    

//****************************** Utilities ***********************//

 
 public static boolean isValid(int i , int j)throws Exception{
   if(i<=n && i>=1 && j <= m && j>= 1 && (!v[i][j])&&(!mat[i][j]) )return true;
   else return false;
 }
 public static void bfs(int xroot, int yroot)throws Exception{
    
        LinkedList <Integer> xq = new LinkedList<Integer>();
        LinkedList <Integer> yq = new LinkedList<Integer>();
        LinkedList <Integer> buff = new LinkedList<Integer>();
        
        int l = 0;//level and will be marked at the time of adding into queue
        LinkedList<Integer> level_q = new LinkedList<Integer>();
        xq.add(xroot);yq.add(yroot);
        v[xroot][yroot]=true;
        //level[root]=0;
        buff.add(xroot);buff.add(yroot);
        int temp_l = 0;
        level_q.add(0);
        while(!xq.isEmpty()){
        
            int ux = xq.removeFirst(); //first
            int uy = yq.removeFirst(); //first
            l = level_q.removeFirst();
            
            //level[u] = l;     
            for(int i = 0 ; i<= 3 ; i++){
                  int vx = ux+dx[i] ; int vy = uy+dy[i];    
                if(isValid(vx ,vy) ){
                    buff.add(vx);
                    buff.add(vy);
                    v[vx][vy]=true;
                    if(mat[vx][vy]){
                        temp_l = Math.max(l+1 , temp_l);
                        si  = ux ; sj = uy;
                    }
                    xq.add(vx);yq.add(vy);
                //  adj[idx(ux,uy)].add(idx(vx , vy));
                //  adj[idx(vx , vy)].add(idx(ux,uy)); 
                    level_q.add(l+1);
                //  f[v]=u;
                //  level[v]=l+1;
                }
            }
        }
        int tot = buff.size()/2;;
        while(!buff.isEmpty()){
        
            int ux = buff.removeFirst(); //first
            int uy = buff.removeFirst(); //first
            
            //level[u] = l;     
            for(int i = 0 ; i<= 3 ; i++){
                int vx = ux+dx[i] ; int vy = uy+dy[i];  
                if(mat[vx][vy] && (t[vx][vy] != id)){
                    arr[vx][vy] += tot;
                    t[vx][vy] = id;
                }
            }
        }       
        //out.write("\n first max level = "+l + " f_end ( x ="+ si+" y="+sj+")\n");
        //out.flush();
        return ;
        
 }
 public static boolean isPrime(long n)throws Exception{
  if(n==1)return false;
  if(n<=3)return true;
  if(n%2==0)return false;
  for(int i=2 ;i <= Math.sqrt(n); i++){
   if(n%i==0)return false;
  }
  return true;
 }
 // sieve
 public static int[] primes(int n)throws Exception{       // for(int i=1;i<=arr.length-1;i++)out.write(""+arr[i]+" ");
  boolean arr[] = new boolean[n+1];
  Arrays.fill(arr,true);
  arr[1]=false;
  for(int i=2;i<=Math.sqrt(n);i++){
    if(!arr[i])continue;
    for(int j = 2*i ;j<=n;j+=i){
        arr[i]=false;
    }
  }
  LinkedList<Integer> ll = new LinkedList<Integer>();
  for(int i=1;i<=n;i++){
   if(arr[i])ll.add(i);
  }
  n = ll.size();
  
  int primes[] = new int[n+1];
  for(int i=1;i<=n;i++){
    primes[i]=ll.removeFirst();
  }
  return primes;
 }
 public static long gcd (long a , long b)throws Exception{
  if(b==0)return a;
  return gcd(b , a%b);
 }
 public static long lcm (long a , long b)throws Exception{
  if(a==0||b==0)return 0;
  return (a*b)/gcd(a,b);
 }
 public static long mulmod(long a , long b ,long mod)throws Exception{
   if(a==0||b==0)return 0;
   if(b==1)return a;
   long ans = mulmod(a,b/2,mod);
   ans = (ans*2)% mod;
   if(b%2==1)ans = (a + ans)% mod;
   return ans;
 }
 public static long pow(long a , long b ,long mod)throws Exception{
   if(b==0)return 1;
   if(b==1)return a;
   long ans = pow(a,b/2,mod);
   ans = (ans * ans)% mod;
   if(b%2==1)ans = (a * ans)% mod;
   return ans;
 }
 // 20*20   nCr Pascal Table
 public static long[][] ncrTable()throws Exception{
  long ncr[][] = new long[21][21];
  for(int i=0 ;i<=20 ;i++){ncr[i][0]=1;ncr[i][i]=1;}
  for(int j=0;j<=20 ;j++){
   for(int i=j+1;i<= 20 ;i++){
    ncr[i][j] = ncr[i-1][j]+ncr[i-1][j-1];
   }
  }
  return ncr;
 }
//*******************************I/O******************************//    
public static int i()throws Exception{
 //return Integer.parseInt(br.readLine().trim());
 return in.nextInt();
}
public static int[] is(int n)throws Exception{
  //int arr[] = new int[n+1];
  for(int i=1 ; i <= n ;i++)tempints[i] = in.nextInt();  
 return tempints;
}
public static long l()throws Exception{
 return in.nextLong();
}
public static long[] ls(int n)throws Exception{
  for(int i=1 ; i <= n ;i++)templongs[i] = in.nextLong();  
 return templongs;
}

public static double d()throws Exception{
 return in.nextDouble();
}
public static double[] ds(int n)throws Exception{
  for(int i=1 ; i <= n ;i++)tempdoubles[i] = in.nextDouble();  
 return tempdoubles;
}
public static char c()throws Exception{
 return in.nextCharacter();
}
public static char[] cs(int n)throws Exception{
  for(int i=1 ; i <= n ;i++)tempchars[i] = in.nextCharacter();  
 return tempchars;
}
public static String s()throws Exception{
 return in.nextLine();
}
public static BigInteger bi()throws Exception{
 return in.nextBigInteger();
}
//***********************I/O ENDS ***********************//
//*********************** 0.3%f [precision]***********************//
/* roundoff upto 2 digits 
   double roundOff = Math.round(a * 100.0) / 100.0;
                    or
   System.out.printf("%.2f", val);
                    
*/
/*
  print upto 2 digits after decimal
  val = ((long)(val * 100.0))/100.0;
  
*/
}

class FastReader{

    private boolean finished = false;

    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
    private SpaceCharFilter filter;

    public FastReader(InputStream stream){
        this.stream = stream;
    }

    public int read(){
        if (numChars == -1){
            throw new InputMismatchException ();
        }
        if (curChar >= numChars){
            curChar = 0;
            try{
                numChars = stream.read (buf);
            } catch (IOException e){
                throw new InputMismatchException ();
            }
            if (numChars <= 0){
                return -1;
            }
        }
        return buf[curChar++];
    }

    public int peek(){
        if (numChars == -1){
            return -1;
        }
        if (curChar >= numChars){
            curChar = 0;
            try{
                numChars = stream.read (buf);
            } catch (IOException e){
                return -1;
            }
            if (numChars <= 0){
                return -1;
            }
        }
        return buf[curChar];
    }

    public int nextInt(){
        int c = read ();
        while (isSpaceChar (c))
            c = read ();
        int sgn = 1;
        if (c == '-'){
            sgn = -1;
            c = read ();
        }
        int res = 0;
        do{
            if(c==','){
                c = read();
            }
            if (c < '0' || c > '9'){
                throw new InputMismatchException ();
            }
            res *= 10;
            res += c - '0';
            c = read ();
        } while (!isSpaceChar (c));
        return res * sgn;
    }

    public long nextLong(){
        int c = read ();
        while (isSpaceChar (c))
            c = read ();
        int sgn = 1;
        if (c == '-'){
            sgn = -1;
            c = read ();
        }
        long res = 0;
        do{
            if (c < '0' || c > '9'){
                throw new InputMismatchException ();
            }
            res *= 10;
            res += c - '0';
            c = read ();
        } while (!isSpaceChar (c));
        return res * sgn;
    }

    public String nextString(){
        int c = read ();
        while (isSpaceChar (c))
            c = read ();
        StringBuilder res = new StringBuilder ();
        do{
            res.appendCodePoint (c);
            c = read ();
        } while (!isSpaceChar (c));
        return res.toString ();
    }

    public boolean isSpaceChar(int c){
        if (filter != null){
            return filter.isSpaceChar (c);
        }
        return isWhitespace (c);
    }

    public static boolean isWhitespace(int c){
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    private String readLine0(){
        StringBuilder buf = new StringBuilder ();
        int c = read ();
        while (c != '\n' && c != -1){
            if (c != '\r'){
                buf.appendCodePoint (c);
            }
            c = read ();
        }
        return buf.toString ();
    }

    public String nextLine(){
        String s = readLine0 ();
        while (s.trim ().length () == 0)
            s = readLine0 ();
        return s;
    }

    public String nextLine(boolean ignoreEmptyLines){
        if (ignoreEmptyLines){
            return nextLine ();
        }else{
            return readLine0 ();
        }
    }

    public BigInteger nextBigInteger(){
        try{
            return new BigInteger (nextString ());
        } catch (NumberFormatException e){
            throw new InputMismatchException ();
        }
    }

    public char nextCharacter(){
        int c = read ();
        while (isSpaceChar (c))
            c = read ();
        return (char) c;
    }

    public double nextDouble(){
        int c = read ();
        while (isSpaceChar (c))
            c = read ();
        int sgn = 1;
        if (c == '-'){
            sgn = -1;
            c = read ();
        }
        double res = 0;
        while (!isSpaceChar (c) && c != '.'){
            if (c == 'e' || c == 'E'){
                return res * Math.pow (10, nextInt ());
            }
            if (c < '0' || c > '9'){
                throw new InputMismatchException ();
            }
            res *= 10;
            res += c - '0';
            c = read ();
        }
        if (c == '.'){
            c = read ();
            double m = 1;
            while (!isSpaceChar (c)){
                if (c == 'e' || c == 'E'){
                    return res * Math.pow (10, nextInt ());
                }
                if (c < '0' || c > '9'){
                    throw new InputMismatchException ();
                }
                m /= 10;
                res += (c - '0') * m;
                c = read ();
            }
        }
        return res * sgn;
    }

    public boolean isExhausted(){
        int value;
        while (isSpaceChar (value = peek ()) && value != -1)
            read ();
        return value == -1;
    }

    public String next(){
        return nextString ();
    }

    public SpaceCharFilter getFilter(){
        return filter;
    }

    public void setFilter(SpaceCharFilter filter){
        this.filter = filter;
    }

    public interface SpaceCharFilter{
        public boolean isSpaceChar(int ch);
    }
}
 /******************** Pair class ***********************/
 
 class Pair implements Comparable<Pair>{
 public int a;
 public int b;
 public Pair(){
  this.a = 0;
  this.b = 0;
 }
 public Pair(int a,int b){
  this.a = a;
  this.b = b;
 }
 public int compareTo(Pair p){
  if(this.a==p.a){
   return this.b-p.b;  
  }
  return this.a-p.a; 
 }
 public String toString(){
  return "a="+this.a+" b="+this.b;
 }
 
} 