Even-Sum Sequence

Time limit1sMemory limit256 MB

Summary

Replace the fewest entries so every length-k window sum is even, then output the lexicographically smallest such sequence.

Level: Medium6 of 10
Topics: Math, Greedy
Solved: No attempts yet

Problem

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.

Input

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$ )

Output

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.

Examples3

Example 1
Input
```
8 3
1 2 3 4 5 6 7 8
```
Expected output
```
3
1 2 3 1 0 1 7 8
```
Example 2
Input
```
1 1
7
```
Expected output
```
1
0
```
Example 3
Input
```
5 1
2 4 6 8 10
```
Expected output
```
0
2 4 6 8 10
```