E. Флаг 2
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
128 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Согласно очередному стандарту ISO, флаг каждой страны должен представлять собой, как ни странно, клетчатое поле размером n × m, каждая клетка которого целиком покрашена в один из 26 цветов. Накладываются следующие ограничения:

  • В каждой строке должно использоваться не более двух различных цветов.
  • Никакие 2 смежные по стороне клетки не должны быть покрашены в один цвет.

Обратите внимание, что в одном столбце может использоваться более двух различных цветов.

Правительство Берляндии решило привести флаг своей страны в соответствие очередному стандарту, при этом как можно меньше изменив старый флаг. По заданному флагу Берляндии вам требуется найти, какое наименьшее число клеток нужно перекрасить, чтобы флаг соответствовал стандарту 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