K. Kool Strings
time limit per test
0.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Professor Kardashi is known for always being fashionable and for her passion for computer science. Her current obsessions are binary strings and efficiency. In particular, she says that a binary string is kool if it does not contain $$$K$$$ or more consecutive identical characters.

To test your skills, Professor Kardashi gives you a binary string $$$S$$$ and allows you to perform the following operation on it: choose an index $$$i$$$ and flip the value of $$$S_i$$$ (changing a '0' to '1' or a '1' to '0').

Your task is to transform $$$S$$$ into a kool string using the minimum number of operations.

Input

The input consists of a single line that contains an integer $$$K$$$ and a binary string $$$S$$$ ($$$2 \leq K \leq |S| \leq 10^5$$$).

Output

Output a single line with an integer indicating the minimum number of operations needed to transform $$$S$$$ into a kool string, followed by a kool string that can be obtained after applying that number of operations to $$$S$$$. If there are multiple solutions, output any of them.

Examples
Input
2 00
Output
1 01
Input
2 10
Output
0 10
Input
3 1111100
Output
1 1101100
Input
3 00001111
Output
2 01001101