CF97A.Domino

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.

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.

小根纳季生日时收到了一副多米诺骨牌。这副骨牌共包含 28 张互不相同的 $2 \times 1$ 多米诺骨牌，每张骨牌的两个半块上各有一个数字，取值范围为 $0$ 到 $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  

若一个由 28 张多米诺骨牌构成的图形能够被恰好 14 个互不相交的 $2 \times 2$ 正方形完全覆盖，且每个正方形内所含的四个数字均相等，则该图形被称为幻方图形（magic figure）。每当根纳季拼出一个幻方图形时，这套骨牌便会显现某种“魔法属性”——他便能赢得下一场竞赛。根纳季注意到：他不能重复拼出已经拼过的图形，否则将由其他人赢得该次竞赛。

根纳季选取了一块大小为 $n \times m$ 的方格纸，并在其上放置了若干尺寸为 $1 \times 2$ 和 $2 \times 1$ 的矩形骨牌（即标准多米诺骨牌形状）。每张骨牌恰好完整覆盖方格纸中两个相邻的格子；这些骨牌彼此不重叠（但可以邻接）。整块方格纸上共放置了恰好 28 张骨牌，与骨牌集合中的总数一致。现在，根纳季希望将每张骨牌替换为一副标准骨牌集合中的一张多米诺骨牌（即从上述 28 张中选），使得最终形成的图形是一个幻方图形。不同位置的骨牌必须替换为不同的多米诺骨牌（即每张骨牌恰好使用一次）。请确定：在给定骨牌初始布局的前提下，根纳季最多能赢得多少场竞赛？此外，还需给出一种具体的骨牌替换方案，使他能赢得下一届 Codeforces 比赛。

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.

第一行包含两个正整数 $n$ 和 $m$（$1 \leq n, m \leq 30$）。接下来的 $n$ 行，每行包含 $m$ 个字符，表示棋盘上筹码的位置。其中点号 . 表示空格，拉丁字母 "a" 到 "z" 以及 "A"、"B" 表示筹码的位置。棋盘上恰好有 28 个筹码。被同一筹码覆盖的方格用相同的字母标记，不同筹码用不同字母标记。保证输入的棋盘描述是合法的。

同时保证至少存在一种解。

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.

第一行输出用多米诺骨牌替换筹码以得到魔法图形的方法数。即，使用该筹码排列所能赢得的比赛总数。接下来的 $n$ 行，每行包含 $m$ 个字符，应输出一个由点号（.）和数字 $0$ 至 $6$ 组成的方阵——任一可行解。所有多米诺骨牌必须互不相同。