Согласно очередному стандарту ISO, флаг каждой страны должен представлять собой, как ни странно, клетчатое поле размером n × m, каждая клетка которого целиком покрашена в один из 26 цветов. Накладываются следующие ограничения:
Обратите внимание, что в одном столбце может использоваться более двух различных цветов.
Правительство Берляндии решило привести флаг своей страны в соответствие очередному стандарту, при этом как можно меньше изменив старый флаг. По заданному флагу Берляндии вам требуется найти, какое наименьшее число клеток нужно перекрасить, чтобы флаг соответствовал стандарту ISO. Также требуется построить один из возможных вариантов нового флага Берляндии.
В первой строке входных данных записаны 2 целых числа n и m (1 ≤ n, m ≤ 500) — число строк и столбцов во флаге Берляндии соответственно. Далее следует описание флага: в следующих n строках содержится по m символов. Каждый символ — буква от a до z, обозначает цвет соответствующей клетки.
В первую строку выходных данных выведите наименьшее число перекрашиваний, требуемое для приведения флага в соответствие новому стандарту ISO. Следующие n строк должны содержать один из возможных вариантов нового флага Берляндии. Не забудьте, что предложенный вами вариант нового флага должен быть получен из старого наименьшим числом перекрашиваний клеток. Если решений несколько выведите любое.
3 4 aaaa bbbb cccc
6 abab baba acac
3 3 aba aba zzz
4 aba bab zbz
2000 ms 128 Mb Правила оформления программ и список ошибок при автоматической проверке задач