Even-Sum Sequence

You are given an integer sequence $a_1, a_2, \dots, a_n$. If $a_i + a_{i+1} + \dots + a_{i+k-1}$ is even for every integer $i$ with $1 \le i \le n - k + 1$, the sequence is called a $k$-even-sum sequence.

You can replace some elements of the sequence with any integers you want. Find the minimum number of elements you have to replace to turn the sequence into a $k$-even-sum sequence, and print the sequence you get.

The first line has the integers $n$ and $k$. ($1 \le k \le n \le 10^6$)

The second line has $n$ integers. The $i$-th of them is $a_i$. ($0 \le a_i \le 10^9$)

On the first line print the minimum number of elements that have to be replaced.

On the second line print the $n$ elements of the finished sequence, separated by single spaces. Every element must satisfy $0 \le a_i \le 2 \times 10^9$.

If several sequences reach that minimum, print the lexicographically smallest one. Between two sequences of the same length, the one holding the smaller value at the first position where they differ comes first.