Цветная полоска представляет собой n расположенных в ряд клеточек, каждая из которых покрашена в один из k цветов. Требуется перекрасить наименьшее количество клеточек так, чтобы никакие две соседние клетки не были одинакового цвета. Перекрашивать клетки можно в любые цвета от 1 до k.
Выходные данные
Выведите единственное число — искомое минимальное количество перекрашиваний. Во вторую строку выведите любой из возможных вариантов полоски после перекрашиваний.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 3
ABBACC
|
2
ABCACA
|
|
2
|
3 2
BBB
|
1
BAB
|