도미노

Little Gennady는 생일 선물로 도미노 한 세트를 받았다. 이 세트는 크기가 2 × 1인 서로 다른 도미노 28개로 이루어져 있다. 각 도미노의 양쪽 절반에는 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개로 이루어진 도형을 크기가 2 × 2인 서로 겹치지 않는 정사각형 14개로 완전히 덮을 수 있고, 각 정사각형에 같은 숫자 네 개가 들어 있다면 이 도형을 마법 도형이라고 한다. Gennady가 마법 도형을 조립할 때마다 세트의 마법 같은 속성이 나타나서 다음 대회에서 우승한다. Gennady는 이미 조립했던 도형을 다시 조립할 수 없다는 것을 알아냈다. 그렇게 하면 다른 누군가가 대회에서 우승하기 때문이다.

Gennady는 크기가 n × m인 격자판을 선택하고 그 위에 크기가 1 × 2 또는 2 × 1인 직사각형 칩을 놓았다. 각 칩은 격자판에서 서로 이웃한 칸 정확히 두 개를 완전히 차지한다. 이 칩들은 서로 겹치지 않지만 맞닿을 수는 있다. 격자판에는 전체적으로 정확히 28개의 칩이 있으며, 이는 세트에 있는 도미노의 개수와 같다. Now Gennady는 각 칩을 도미노로 바꾸어 그 결과로 마법 도형이 나타나게 하려고 한다. 서로 다른 칩은 서로 다른 도미노로 바꾸어야 한다. 주어진 칩 배치로 Gennady가 몇 번의 대회에서 우승할 수 있는지 구한다. 또한 다음 Codeforces 라운드에서 우승할 수 있도록 칩을 도미노로 바꾸는 가능한 방법 중 하나를 찾아야 한다.

첫째 줄에 양의 정수 n와 m가 주어진다 (1 ≤ n, m ≤ 30). 이어지는 n개의 줄에는 각각 칩이 격자판에 놓인 상태를 나타내는 m개의 문자가 주어진다. 점은 빈칸을 나타내며, "a"부터 "z"까지의 라틴 문자와 "A", "B"는 칩의 위치를 나타낸다. 격자판에는 정확히 28개의 칩이 있다. 같은 칩이 덮는 칸들은 같은 문자로 표시되고, 서로 다른 칩들은 서로 다른 문자로 표시된다. 격자판의 설명이 올바름이 보장된다.

또한 적어도 하나의 해가 존재함이 보장된다.

첫째 줄에 칩을 도미노로 바꾸어 마법 도형을 만드는 방법의 수를 출력한다. 이는 이 칩 배치를 사용하여 우승할 수 있는 대회의 총횟수이다. 이어지는 n개의 줄에는 각각 m개의 문자를 출력해야 하며, 점과 0부터 6까지의 숫자로 이루어진 격자판으로 가능한 해 중 하나를 나타내야 한다. 모든 도미노는 서로 달라야 한다.