C. Цветная полоска
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Цветная полоска представляет собой n расположенных в ряд клеточек, каждая из которых покрашена в один из k цветов. Требуется перекрасить наименьшее количество клеточек так, чтобы никакие две соседние клетки не были одинакового цвета. Перекрашивать клетки можно в любые цвета от 1 до k.

Входные данные

В первой строке входных данных записано два целых числа n и k (1 ≤ n ≤ 5·105; 2 ≤ k ≤ 26). Вторая строка состоит из n прописных букв латинского алфавита. Буква «A» обозначает первый цвет, «B» — второй и так далее. В строке используются только первые k букв латинского алфавита. Каждая буква обозначает цвет соответствующей клетки полоски.

Выходные данные

Выведите единственное число — искомое минимальное количество перекрашиваний. Во вторую строку выведите любой из возможных вариантов полоски после перекрашиваний.

Примеры
Входные данные
6 3
ABBACC
Выходные данные
2
ABCACA
Входные данные
3 2
BBB
Выходные данные
1
BAB