遥远王国的秋天来得很晚。庄稼丰收,现在是为过冬做准备的时候了。当大多数人庆祝丰收节时,看门人西蒙试图解决一项非常重要的任务:如何在仓库中为农业设备找到位置。
他在使用一些特别大的设备时遇到了问题,当然就是涡轮喷气机。问题是,当涡轮喷气机被存放时,它占用的不仅仅是一些简单的矩形空间。它占据了一个T形空间,如下四张图之一(这里字符“#”代表涡轮增压器占用的空间,字符“.”代表可用空间):
### ..# .#. #...#. ### .#. ###.#. ..# ### #..
Simon 面临着一个非常自然的挑战:在给定的 n × m 单元格仓库中放置最大数量的涡轮犁。当一个人存放涡轮犁时,他可以以任何方式旋转它们(以便它们占据像上面四张图片之一一样的空间)。然而,两台涡轮犁不能“重叠”,即它们不能共享仓库中的同一个单元。
Simon 认为他无法独自找到在仓库中放置插头的最佳方式,以最大限度地提高其数量。你能帮助他吗?
输入
唯一的一行包含两个空格分隔的整数 n 和 m — 仓库的大小 (1 ≤ n, m ≤ 9)。
输出
在第一行中打印可以放置在仓库中的涡轮犁的最大数量。在接下来的 n 行中,每一行打印 m 个字符。使用 ”。” (点)来标记空白空间,并使用连续的大写拉丁字母(“A”表示第一个涡轮犁,“B”表示第二个,依此类推,直到达到方案中的涡轮犁数量)来标记相应涡轮犁的位置,考虑到它们在仓库中的最佳位置。涡轮犁位置的编号顺序并不重要。如果对于给定大小的仓库有多个最佳解决方案,请打印其中任何一个。
示例
输入 #1
3 3
输出 #1
1 AAA .A. .A.
输入 #2
5 6
输出 #2
4 A..C.. AAAC.. ABCCCD .B.DDD BBB..D
输入 #3
2 2
输出 #3
0 .. ..