根据新的ISO标准,奇怪的是,每个国家的国旗都应该有一个n×m的方格区域,每个方格都应该涂上26种颜色中的一种。设置了以下限制:
- 每行最多可以使用两种不同的颜色。
- 两个相邻的方块不能涂成相同的颜色。
请注意,在一列中可以使用两种以上不同的颜色。
Berland 政府决定根据新标准对本国国旗进行更改,同时他们希望这些更改最小化。根据 Berland 旗帜的给定描述,您应该找出需要涂成不同颜色的最小方块数量,以使旗帜符合新的 ISO 标准。您也可以建造新伯兰国旗的可能变体之一。
输入
第一个输入行包含 2 个整数 n 和 m (1 ≤ n, m ≤ 500) — 分别是 Berland 标志中的行数和列数。接下来是标志的描述:接下来的 n 行每行包含 m 个字符。每个字符都是a到z的字母,代表对应方块的颜色。
输出
在第一行中输出需要重新绘制的最小方块数量,以使标志符合新的 ISO 标准。以下 n 行应包含新标志的可能变体之一。不要忘记,您提出的旗帜变体应该源自旧旗帜,并且重新绘制的方块数量最少。如果答案不唯一,则输出任何一个。
示例
输入 #1
3 4 aaaa bbbb cccc
输出 #1
6 abab baba acac
输入 #2
3 3 aba aba zzz
输出 #2
4 aba bab zbz