시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 2048 MB56393574.468%

문제

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.

입력

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

출력

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.

예제 입력 1

2 00

예제 출력 1

1 01

예제 입력 2

2 10

예제 출력 2

0 10

예제 입력 3

3 1111100

예제 출력 3

1 1101100

예제 입력 4

3 00001111

예제 출력 4

2 01001101