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.util.InputMismatchException;
import java.math.BigInteger;
import java.util.*;
import java.util.List;
import java.util.Iterator;
import java.util.Comparator;
import java.util.Arrays;
import java.util.NoSuchElementException;
import java.util.NavigableSet;
import java.util.Map;
import java.util.Collections;
import java.util.HashMap;
import java.util.Collection;
import java.util.ArrayList;
import java.io.*;

/**
 * Generated by Contest helper plug-in
 * Actual solution is at the bottom
 */
public class Main {
	public static void main(String[] args) {
		InputReader in = new StreamInputReader(System.in);
		PrintWriter out = new PrintWriter(System.out);
		run(in, out);
	}

	public static void run(InputReader in, PrintWriter out) {
		Solver solver = new TaskA();
		solver.solve(1, in, out);
		Exit.exit(in, out);
	}
}

abstract class InputReader {
	private boolean finished = false;

	public abstract int read();

	public int readInt() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int 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 readString() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuffer res = new StringBuffer();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isSpaceChar(c));
		return res.toString();
	}

	private boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}

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

	public void setFinished(boolean finished) {
		this.finished = finished;
	}

	public abstract void close();
}

class StreamInputReader extends InputReader {
	private InputStream stream;
	private byte[] buf = new byte[1024];
	private int curChar, numChars;

	public StreamInputReader(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 void close() {
		try {
			stream.close();
		} catch (IOException ignored) {
		}
	}
}

class Exit {
	private Exit() {
	}

	public static void exit(InputReader in, PrintWriter out) {
		in.setFinished(true);
		in.close();
		out.close();
	}
}

interface Solver {
	public void solve(int testNumber, InputReader in, PrintWriter out);
}

abstract class ReadOnlyIterator<T> implements Iterator<T>  {
	public final void remove() {
		throw new UnsupportedOperationException();
	}
}

abstract class AbstractSequence<T> implements Sequence<T> {

	protected void checkIndices(int from, int to, int size) {
		if (from < 0 || to < 0 || from > size || to > size || from > to)
			throw new IndexOutOfBoundsException();
	}

	public Iterator<T> iterator() {
		return new ReadOnlyIterator<T>() {
			private int index = 0;

			public boolean hasNext() {
				return index != size();
			}

			public T next() {
				if (!hasNext())
					throw new NoSuchElementException();
				return get(index++);
			}
		};
	}

	protected class SubSequence implements Sequence<T> {
		protected final int from;
		protected final int to;

		public SubSequence(int from, int to) {
			this.from = from;
			this.to = to;
		}

		public int size() {
			return to - from;
		}

		public T get(int index) {
			if (index < 0 || index >= size())
				throw new IndexOutOfBoundsException();
			return AbstractSequence.this.get(from + index);
		}

		public Iterator<T> iterator() {
			return new ReadOnlyIterator<T>() {
				private int index = from;

				public boolean hasNext() {
					return index != to;
				}

				public T next() {
					if (index == to)
						throw new NoSuchElementException();
					return AbstractSequence.this.get(index++);
				}
			};
		}
	}
}

abstract class AbstractWritableSequence<T> extends AbstractSequence<T> implements WritableSequence<T> {
	public WritableSequence<T> subSequence(int from) {
		return subSequence(from, size());
	}

	public WritableSequence<T> subSequence(int from, int to) {
		int size = size();
		if (from < 0)
			from += size;
		if (to < 0)
			to += size;
		checkIndices(from, to, size);
		return new WritableSubSequence(from, to);
	}

	protected class WritableSubSequence extends SubSequence implements WritableSequence<T>{
		public WritableSubSequence(int from, int to) {
			super(from, to);
		}

		public void set(int index, T value) {
			if (index < 0 || index >= size())
				throw new IndexOutOfBoundsException();
			AbstractWritableSequence.this.set(from + index, value);
		}

		public WritableSequence<T> subSequence(int from) {
			return subSequence(from, to);
		}

		public WritableSequence<T> subSequence(int from, int to) {
			int size = size();
			if (from < 0)
				from += size;
			if (to < 0)
				to += size;
			checkIndices(from, to, size);
			return new WritableSubSequence(from + this.from, to + this.from);
		}
	}
}

abstract class ArrayWrapper<T> extends AbstractWritableSequence<T> {

	public static WritableSequence<Integer> wrap(int...array) {
		return new IntArrayWrapper(array);
	}

	protected static class IntArrayWrapper extends ArrayWrapper<Integer> {
		protected final int[] array;

		protected IntArrayWrapper(int[] array) {
			this.array = array;
		}

		public int size() {
			return array.length;
		}

		public Integer get(int index) {
			return array[index];
		}

		public void set(int index, Integer value) {
			array[index] = value;
		}
	}

	}

interface Sequence<T> extends Iterable<T> {
	public int size();
	public T get(int index);
}

class SequenceUtils {

	public static<T extends Comparable<T>> boolean nextPermutation(WritableSequence<T> sequence) {
		for (int i = sequence.size() - 2; i >= 0; i--) {
			if (sequence.get(i).compareTo(sequence.get(i + 1)) < 0) {
				int index = i + 1;
				for (int j = i + 2; j < sequence.size(); j++) {
					if (sequence.get(i).compareTo(sequence.get(j)) >= 0)
						break;
					else
						index = j;
				}
				T temp = sequence.get(i);
				sequence.set(i, sequence.get(index));
				sequence.set(index, temp);
				sort(sequence.subSequence(i + 1));
				return true;
			}
		}
		return false;
	}

	public static<T extends Comparable<T>> WritableSequence<T> sort(WritableSequence<T> sequence) {
		return sort(sequence, null);
	}

	public static<T> WritableSequence<T> sort(WritableSequence<T> sequence, Comparator<? super T> comparator) {
		makeHeap(sequence, comparator);
		for (int i = sequence.size() - 1; i > 0; i--) {
			T temp = sequence.get(0);
			sequence.set(0, sequence.get(i));
			sequence.set(i, temp);
			siftDown(sequence, 0, i, comparator);
		}
		return sequence;
	}

	private static<T> WritableSequence<T> makeHeap(WritableSequence<T> sequence, Comparator<? super T> comparator) {
		int length = sequence.size();
		for (int i = length / 2 - 1; i >= 0; i--)
			siftDown(sequence, i, length, comparator);
		return sequence;
	}

	private static<T> void siftDown(WritableSequence<T> sequence, int start, int end, Comparator<? super T> comparator) {
		int root = start;
		while (2 * root + 1 < end) {
			int childIndex = 2 * root + 1;
			if (childIndex + 1 < end && compare(sequence.get(childIndex), sequence.get(childIndex + 1), comparator) < 0)
				childIndex++;
			if (compare(sequence.get(childIndex), sequence.get(root), comparator) <= 0)
				return;
			T temp = sequence.get(root);
			sequence.set(root, sequence.get(childIndex));
			sequence.set(childIndex, temp);
			root = childIndex;
		}
	}

	private static<T> int compare(T first, T second, Comparator<? super T> comparator) {
		if (comparator != null)
			return comparator.compare(first, second);
		//noinspection unchecked
		return ((Comparable<? super T>)first).compareTo(second);
	}

	}

interface WritableSequence<T> extends Sequence<T> {
	public void set(int index, T value);
	public WritableSequence<T> subSequence(int from);
	}

class IOUtils {

	public static char[] readCharArray(InputReader in, int size) {
		char[] array = new char[size];
		for (int i = 0; i < size; i++)
			array[i] = in.readCharacter();
		return array;
	}

	public static char[][] readTable(InputReader in, int rowCount, int columnCount) {
		char[][] table = new char[rowCount][];
		for (int i = 0; i < rowCount; i++)
			table[i] = readCharArray(in, columnCount);
		return table;
	}

	}

class IntegerUtils {

	public static long factorial(int n) {
		long result = 1;
		for (int i = 2; i <= n; i++)
			result *= i;
		return result;
	}

	}

class TaskA implements Solver {
	public void solve(int testNumber, InputReader in, PrintWriter out) {
		int rowCount = in.readInt();
		int columnCount = in.readInt();
		char[][] table = IOUtils.readTable(in, rowCount, columnCount);
		int[][] index = new int[rowCount][columnCount];
		boolean[][] graph = new boolean[15][15];
		int color = 1;
		for (int i = 0; i < rowCount; i++) {
			for (int j = 0; j < columnCount; j++) {
				if (table[i][j] != '.' && index[i][j] == 0) {
					index[i][j] = color;
					index[i + 1][j] = color;
					index[i][j + 1] = color;
					index[i + 1][j + 1] = color++;
				}
			}
		}
		for (int i = 0; i < 28; i++) {
			char symbol;
			if (i < 26)
				symbol = (char) ('a' + i);
			else
				symbol = (char) ('A' + i - 26);
			outer:
			for (int j = 0; j < rowCount; j++) {
				for (int k = 0; k < columnCount; k++) {
					if (table[j][k] == symbol) {
						int otherRow = j;
						int otherColumn = k;
						if (j + 1 < rowCount && table[j + 1][k] == symbol)
							otherRow = j + 1;
						else
							otherColumn = k + 1;
						graph[index[j][k]][index[otherRow][otherColumn]] = graph[index[otherRow][otherColumn]][index[j][k]] = true;
						break outer;
					}
				}
			}
		}
		int nonDoubleCount = 0;
		for (int i = 1; i <= 14; i++) {
			if (!graph[i][i])
				nonDoubleCount++;
		}
		int[] doubleIndices = new int[14 - nonDoubleCount];
		int[] nonDoubleIndices = new int[nonDoubleCount];
		int doubleIndex = 0;
		int nonDoubleIndex = 0;
		for (int i = 1; i <= 14; i++) {
			if (graph[i][i])
				doubleIndices[doubleIndex++] = i;
			else
				nonDoubleIndices[nonDoubleIndex++] = i;
		}
		long answer = 0;
		WritableSequence<Integer> permutation = ArrayWrapper.wrap(nonDoubleIndices);
		do {
			boolean good = true;
			for (int i = 7; i < nonDoubleIndex - 1; i++) {
				if (nonDoubleIndices[i] > nonDoubleIndices[i + 1])
					good = false;
			}
			for (int i = 0; i < 7 && good; i++) {
				int firstI = i >= doubleIndex ? nonDoubleIndices[7 + i - doubleIndex] : doubleIndices[i];
				int secondI = nonDoubleIndices[i];
				if (i >= doubleIndex && firstI > secondI) {
					good = false;
					break;
				}
				for (int j = 0; j < 7 && good; j++) {
					int firstJ = j >= doubleIndex ? nonDoubleIndices[7 + j - doubleIndex] : doubleIndices[j];
					int secondJ = nonDoubleIndices[j];
					if (!graph[firstI][firstJ] && !graph[firstI][secondJ] && !graph[secondI][firstJ] && !graph[secondI][secondJ])
						good = false;
				}
			}
			if (good) {
				if (answer == 0) {
					for (int i = 0; i < rowCount; i++) {
						for (int j = 0; j < columnCount; j++) {
							if (table[i][j] == '.')
								continue;
							for (int k = 0; k < doubleIndex; k++) {
								if (index[i][j] == doubleIndices[k]) {
									table[i][j] = (char) ('0' + k);
									break;
								}
							}
							for (int k = 0; k < nonDoubleIndex; k++) {
								if (index[i][j] == nonDoubleIndices[k]) {
									if (k < 7)
										table[i][j] = (char) ('0' + k);
									else
										table[i][j] = (char) ('0' + doubleIndex + k - 7);
									break;
								}
							}
						}
					}
				}
				answer++;
			}
		} while (SequenceUtils.nextPermutation(permutation));
		answer *= IntegerUtils.factorial(7);
		out.println(answer);
		for (char[] row : table)
			out.println(row);
	}
}

