Problem H. Heron statues

Author:A. Klenin, I. Blinov   Time limit:1 sec
Input file:Standard input   Memory limit:256 Mb
Output file:Standard output  

Statement

Elephant Pakhom installed a row of n statues of herons, each statue is painted in its own color. Colors are represented by small Latin letters from 'a' to 'z'. The elephant is pleased with the result of his work, but now he wants to repaint some statues so that there are no three consecutive statues of the same color. Since Pakhom has tired during the construction of the statues, he wants to repaint as few herons as possible.

Input format

The first line of the input contains integer n. The second line contains n characters — description of statue colors.

Output format

Output must contain a string of length n — a new coloring of herons. If there are several optimal colorings, output any of them.

Constraints

1 ≤ n ≤ 105

Sample tests

No. Standard input Standard output
1
5
aaaaa
aazaa
2
10
asdfghjklz
asdfghjklz

0.087s 0.014s 13