97_A. Domino_16083
Little Gennady was presented with a set of domino for his birthday. The set consists of 28 different dominoes of size 2 × 1. Both halves of each domino contain one digit from 0 to 6. 
    
    
    0-0 0-1 0-2 0-3 0-4 0-5 0-6  
    1-1 1-2 1-3 1-4 1-5 1-6  
    2-2 2-3 2-4 2-5 2-6  
    3-3 3-4 3-5 3-6  
    4-4 4-5 4-6  
    5-5 5-6  
    6-6  
    

The figure that consists of 28 dominoes is called magic, if it can be fully covered with 14 non-intersecting squares of size 2 × 2 so that each square contained four equal numbers. Every time Gennady assembles a magic figure, some magic properties of the set appear — he wins the next contest. Gennady noticed that he can't assemble a figure that has already been assembled, otherwise someone else wins the contest.

<image>

Gennady chose a checked field of size n × m and put there rectangular chips of sizes 1 × 2 and 2 × 1. Each chip fully occupies exactly two neighboring squares of the field. Those chips do not overlap but they can touch each other. Overall the field has exactly 28 chips, equal to the number of dominoes in the set. Now Gennady wants to replace each chip with a domino so that a magic figure appeared as a result. Different chips should be replaced by different dominoes. Determine in what number of contests Gennady can win over at the given position of the chips. You are also required to find one of the possible ways of replacing chips with dominoes to win the next Codeforces round.

Input

The first line contains two positive integers n and m (1 ≤ n, m ≤ 30). Each of the following n lines contains m characters, which is the position of chips on the field. The dots stand for empty spaces, Latin letters from "a" to "z" and "A", "B" stand for the positions of the chips. There are exactly 28 chips on the field. The squares covered by the same chip are marked by the same letter, different chips are marked by different letters. It is guaranteed that the field's description is correct.

It is also guaranteed that at least one solution exists.

Output

Print on the first line the number of ways to replace chips with dominoes to get a magic figure. That is the total number of contests that can be won using this arrangement of the chips. Next n lines containing m characters each, should contain a field from dots and numbers from 0 to 6 — any of the possible solutions. All dominoes should be different.

Examples

Input

8 8
.aabbcc.
.defghi.
kdefghij
klmnopqj
.lmnopq.
.rstuvw.
xrstuvwy
xzzAABBy


Output

10080
.001122.
.001122.
33440055
33440055
.225566.
.225566.
66113344
66113344
import java.io.*;
import java.util.*;


public class Main {
	
	boolean[][] c;
	boolean outputed;
	int[][] a;
	int calc(int[] sq,int color){
		int result=0;
		if(color!=7){
			int[] sq1=new int[14];
			for(int j=0;j<14;j++){
				sq1[j]=sq[j];
			}
			
			for(int i=0;i<14;i++){
				if(sq1[i]==-1){				
					sq1[i]=color;
					break;
				}
			}
			for(int i=0;i<14;i++){
				if(sq1[i]==-1){
					sq1[i]=color;
					result+=calc(sq1,color+1);
					sq1[i]=-1;
				}
			}
		}
		else{
			boolean[] b=new boolean[56];
			for(int i=0;i<56;i++)b[i]=false;
			boolean good=true;
			for(int i=0;i<c.length&&good;i++)
				for(int j=i;j<c[i].length;j++){
					if(c[i][j]) {
						int q=Math.max(sq[i], sq[j]);
						int w=Math.min(sq[i], sq[j]);
						int v=w*7+q;
						if(b[v]){
							good=false;
							break;
						}
						else
							b[v]=true;
						
					}
				}
			if(good) {
				result=1;
				if(!outputed){
					outputed=true;
					for(int i=0;i<a.length;i++){
						for(int j=0;j<a[i].length;j++){
							if(a[i][j]!=-1)a[i][j]=sq[a[i][j]];
						}
						
					}
				}
			}
		}
		return result;
	}
	
	void solve() throws IOException {
		int n=nextInt();
		int m=nextInt();
		String[] field=new String[n];
		for(int i=0;i<n;i++)
			field[i]=nextToken();
		a=new int[n][m];
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++)
				a[i][j]=-1;
		int k=0;
		for(int i=0;i<n-1;i++){
			for(int j=0;j<m-1;j++){
				if(a[i][j]==-1&&field[i].charAt(j)!='.')
					a[i][j]=a[i+1][j]=a[i][j+1]=a[i+1][j+1]=k++;
			}
		}
		c=new boolean[14][14];
		for(int i=0;i<14;i++)
			for(int j=0;j<14;j++)
				c[i][j]=false;
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++){
				if(field[i].charAt(j)!='.'){
					if(i<n-1&&field[i].charAt(j)==field[i+1].charAt(j))
						c[a[i][j]][a[i+1][j]]=c[a[i+1][j]][a[i][j]]=true;
					if(j<m-1&&field[i].charAt(j)==field[i].charAt(j+1))
						c[a[i][j]][a[i][j+1]]=c[a[i][j+1]][a[i][j]]=true;
				}
			}
		int[] sq=new int[14];		
		for(int i=0;i<14;i++)sq[i]=-1;
		out.println((long)calc(sq,0)*5040);
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++)
				if(a[i][j]==-1)
					out.print('.');
				else
					out.print(a[i][j]);
			out.println();
		}
	}

	public static void main(String[] args) throws IOException {
		new Main().run();
	}

	void run() throws IOException {
		reader = new BufferedReader(new InputStreamReader(System.in));
		tokenizer = null;
		out = new PrintWriter(new OutputStreamWriter(System.out));
		solve();
		reader.close();
		out.flush();

	}

	BufferedReader reader;
	StringTokenizer tokenizer;
	PrintWriter out;

	int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}

	String nextToken() throws IOException {
		while (tokenizer == null || !tokenizer.hasMoreTokens()) {
			tokenizer = new StringTokenizer(reader.readLine());
		}
		return tokenizer.nextToken();
	}
}
