小根纳迪生日时收到了一套多米诺骨牌。该套装由 28 块大小为 2 × 1 的不同多米诺骨牌组成。每块多米诺骨牌的两半都包含从 0 到 6 的一位数字。
由 28 块多米诺骨牌组成的图形,如果可以用 14 个大小为 2 × 2 的不相交的正方形完全覆盖,并且每个正方形包含四个相等的数字,则该图形称为魔术。每当根纳迪组装一个魔法人物时,该套装的一些魔法属性就会出现——他赢得了下一场比赛。根纳迪注意到他无法组装已经组装好的人物,否则其他人会赢得比赛。
根纳迪选择了一个大小为 n × m 的检查区域,并在那里放置了大小为 1 × 2 和 2 × 1 的矩形芯片。每个芯片完全占据了该区域的两个相邻正方形。这些芯片不重叠,但可以相互接触。整个场地总共有 28 个筹码,等于该组多米诺骨牌的数量。现在根纳迪想用多米诺骨牌代替每块芯片,这样就会出现一个神奇的人物。不同的芯片应该由不同的多米诺骨牌代替。确定根纳迪在给定的筹码位置上可以赢得多少场比赛。您还需要找到一种用多米诺骨牌替换芯片的可能方法,以赢得下一轮 Codeforces。
输入
第一行包含两个正整数 n 和 m (1 ≤ n, m ≤ 30)。接下来的n行每行包含m个字符,即筹码在场上的位置。点代表空白,拉丁字母“a”到“z”以及“A”、“B”代表筹码的位置。场上正好有 28 个筹码。同一芯片所覆盖的方格用相同的字母标记,不同的芯片所覆盖的方格用不同的字母标记。保证该字段的描述是正确的。
还保证至少存在一个解。
输出
在第一行打印用多米诺骨牌代替芯片以获得魔法数字的方法数。这是使用这种筹码排列可以赢得的比赛总数。接下来的 n 行每行包含 m 个字符,应包含一个由点和 0 到 6 之间的数字组成的字段 - 任何可能的解决方案。所有的多米诺骨牌都应该不同。
示例
输入 #1
8 8 .aabbcc. .defghi. kdefghij klmnopqj .lmnopq. .rstuvw. xrstuvwy xzzAABBy
输出 #1
10080 .001122. .001122. 33440055 33440055 .225566. .225566. 66113344 66113344