시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (하단 참고) 256 MB 110 49 24 54.545%

문제

정수 수열 a1, a2, ..., an이 있을 때, 1 ≤ i ≤ n − k + 1 인 모든 정수 i에 대해서, ai + ai+1 + ... + ai+k−1 이 짝수라면, 이 수열을 k-짝합 수열이라고 정의한다.

당신은 수열에 있는 몇 개의 원소를 원하는 정수로 바꿀 수 있다. 최소 몇 개의 원소를 바꿔야지 수열을 k-짝합 수열로 만들 수 있는가?

입력

첫 번째 줄에는 정수 n, k가 주어진다. (1 ≤ k ≤ n ≤ 106)

두 번째 줄에는 n개의 정수가 주어진다. 이 중 i 번째 정수는 ai(0 ≤ ai ≤ 109) 를 뜻한다.

출력

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

둘째 줄에는 어떻게 원소를 바꿔야하는지 출력한다. 바뀐 정수는 (0 ≤ ai ≤ 2×109) 을 만족해야 한다.

예제 입력 1

8 3
1 2 3 4 5 6 7 8

예제 출력 1

3
1 2 3 5 6 7 7 8

시간 제한 안내

아래 적혀있지 않은 시간 제한은 언어 도움말에 적혀있는 기준을 따른다.

  • Java: 4초
  • Java (OpenJDK): 4초
  • Java 11: 4초
  • Kotlin (JVM): 4초

채점

  • 예제는 채점하지 않는다.