Nikolay 得到了一个长度为 $$$n$$$ 的字符串 $$$s$$$,该字符串仅由小写拉丁字母“a”和“b”组成。其仓位编号从 $$$1$$$ 到 $$$n$$$。
他想要修改他的字符串,以便其每个偶数长度的前缀都具有相同数量的字母“a”和“b”。为了实现这一点,Nikolay 可以执行以下操作任意次数(可能为零):选择字符串中的某个位置并将该位置上的字母替换为另一个字母(即用“b”替换“a”或用“a”替换“b”)。尼古拉不能使用除“a”和“b”之外的任何字母。
长度为 $$$l$$$ ($$$1 \le l \le n$$$) 的字符串 $$$s$$$ 的前缀是字符串 $$$s[1..l]$$$。
例如,对于字符串$$$s=$$$"abba",有两个偶数长度的前缀。第一个是$$$s[1\dots2]=$$$"ab",第二个$$$s[1\dots4]=$$$"abba"。它们都有相同数量的“a”和“b”。
你的任务是计算 Nikolay 必须对字符串 $$$s$$$ 执行的最少操作次数来修改它,以便其每个偶数长度的前缀都具有相等数量的字母“a”和“b”。
输入
输入的第一行包含一个偶数 $$$n$$$ $$$(2 \le n \le 2\cdot10^{5})$$$ — 字符串 $$$s$$$ 的长度。
输入的第二行包含长度为 $$$n$$$ 的字符串 $$$s$$$,该字符串仅由小写拉丁字母“a”和“b”组成。
输出
在第一行中,打印 Nikolay 必须对字符串 $$$s$$$ 执行的最少操作数以对其进行修改,以便其每个偶数长度的前缀都具有相等数量的字母“a”和“b”。
在第二行中打印 Nikolay 在应用所有操作后获得的字符串。如果有多个答案,您可以打印其中任何一个。
示例
输入 #1
4 bbbb
输出 #1
2 abba
输入 #2
6 ababab
输出 #2
0 ababab
输入 #3
2 aa
输出 #3
1 ba
注意
在第一个示例中,Nikolay 必须执行两个操作。例如,他可以将第一个“b”替换为“a”,将最后一个“b”替换为“a”。
在第二个示例中,Nikolay 不需要执行任何操作,因为初始字符串的偶数长度的每个前缀已经包含相同数量的字母“a”和“b”。