Согласно очередному стандарту ISO, флаг каждой страны должен представлять собой, как ни странно, клетчатое поле размером n × m, каждая клетка которого целиком покрашена в один из 26 цветов. Накладываются следующие ограничения:
- В каждой строке должно использоваться не более двух различных цветов.
- Никакие 2 смежные по стороне клетки не должны быть покрашены в один цвет.
Обратите внимание, что в одном столбце может использоваться более двух различных цветов.
Правительство Берляндии решило привести флаг своей страны в соответствие очередному стандарту, при этом как можно меньше изменив старый флаг. По заданному флагу Берляндии вам требуется найти, какое наименьшее число клеток нужно перекрасить, чтобы флаг соответствовал стандарту ISO. Также требуется построить один из возможных вариантов нового флага Берляндии.
Выходные данные
В первую строку выходных данных выведите наименьшее число перекрашиваний, требуемое для приведения флага в соответствие новому стандарту ISO. Следующие n строк должны содержать один из возможных вариантов нового флага Берляндии. Не забудьте, что предложенный вами вариант нового флага должен быть получен из старого наименьшим числом перекрашиваний клеток. Если решений несколько выведите любое.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 4
aaaa
bbbb
cccc
|
6
abab
baba
acac
|
|
2
|
3 3
aba
aba
zzz
|
4
aba
bab
zbz
|