Problem: A colored stripe is represented by a horizontal row of n square cells, each cell is pained one of k colors. Your task is to repaint the minimum number of cells so that no two neighbouring cells are of the same color. You can use any color from 1 to k to repaint the cells.

Input

The first input line contains two integers n and k (1 ≤ n ≤ 5·105; 2 ≤ k ≤ 26). The second line contains n uppercase English letters. Letter "A" stands for the first color, letter "B" stands for the second color and so on. The first k English letters may be used. Each letter represents the color of the corresponding cell of the stripe.

Output

Print a single integer — the required minimum number of repaintings. In the second line print any possible variant of the repainted stripe.

Examples

Input

6 3
ABBACC


Output

2
ABCACA


Input

3 2
BBB


Output

1
BAB

Solution (in PYTHON3):

Solution:
#  =========     /\       /|    |====/|
#      |        /  \       |    |   / |
#      |       /____\      |    |  /  |
#      |      /      \     |    | /   |
#  ========= /        \  =====  |/====|  
#  code

def main():
    n , k = map(int , input().split())
    s = list(input())

    if k > 2:
        ans = 0
        for idx , i in enumerate(s):
            if idx == 0:
                continue
            if s[idx] == s[idx - 1]:
                for j in range(k):
                    c = chr(65 + j)
                    if s[idx] == c:
                        continue
                    elif idx + 1 < n:
                        if s[idx + 1] == c:
                            continue
                    s[idx] = c
                    ans += 1
                    break
        print(ans)
        print(''.join(s))
    else:
        pat1 = 'AB' * n
        ans1 = 0
        for idx , i in enumerate(s):
            if i != pat1[idx]:
                ans1 += 1
        
        pat2 = 'BA' * n
        ans2 = 0
        for idx , i in enumerate(s):
            if i != pat2[idx]:
                ans2 += 1

        if ans1 <= ans2:
            print(ans1)
            print(pat1[:n])
        else:
            print(ans2)
            print(pat2[:n])

    return

if __name__ == "__main__":
    main()