짝합 수열

정수 수열 $a_1, a_2, \dots, a_n$이 주어진다. $1 \le i \le n - k + 1$인 모든 정수 $i$에 대해 $a_i + a_{i+1} + \dots + a_{i+k-1}$이 짝수이면, 이 수열을 $k$-짝합 수열이라고 한다.

수열의 원소 몇 개를 원하는 정수로 바꿀 수 있다. 수열을 $k$-짝합 수열로 만들려면 최소 몇 개의 원소를 바꿔야 하는지 구하고, 그렇게 만든 수열을 출력한다.

첫째 줄에 정수 $n$과 $k$가 주어진다. ($1 \le k \le n \le 10^6$)

둘째 줄에 $n$개의 정수가 주어진다. 그중 $i$번째 정수가 $a_i$이다. ($0 \le a_i \le 10^9$)

첫째 줄에 바꿔야 하는 원소의 최소 개수를 출력한다.

둘째 줄에 완성된 수열의 원소 $n$개를 공백 하나로 구분해 출력한다. 모든 원소는 $0 \le a_i \le 2 \times 10^9$을 만족해야 한다.

바꾸는 원소의 개수가 최소인 수열이 여러 개면 그중 사전순으로 가장 앞서는 것을 출력한다. 길이가 같은 두 수열은 값이 처음으로 달라지는 위치에서 더 작은 값을 가진 쪽이 사전순으로 앞선다.