포스터화

Professor Ibrahim는 알고리즘 수업의 기말 과제를 준비했다. 그는 학생들에게 Posterization Image Filter를 구현하라고 했다.

학생들의 알고리즘은 정수 배열을 대상으로 테스트되며, 여기서 i-th 정수는 이미지의 i-th 픽셀의 색상을 나타낸다. 이미지는 흑백이므로 각 픽셀의 색상은 0 이상 255 이하의 정수이다.

필터를 구현하기 위해 학생들은 흑백 색상 범위 $[0, 255]$를 연속한 색상들로 이루어진 그룹들로 나누고, 각 그룹에서 하나의 색상을 그 그룹의 키로 선택해야 한다. 이미지의 세부 정보를 보존하기 위해 그룹의 크기는 k보다 커서는 안 되며, 각 색상은 정확히 하나의 그룹에 속해야 한다.

마지막으로 학생들은 배열에 있는 각 픽셀의 색상을 그 색상에 할당된 그룹 키로 교체한다.

효과를 더 잘 이해할 수 있도록, 오른쪽으로 갈수록 k가 증가하도록 Posterization Filter를 적용한 일광욕 중인 거북이의 이미지를 아래에 제시한다.

최종 답을 확인하는 과정을 더 쉽게 만들기 위해, Professor Ibrahim는 학생들이 가능한 한 사전순으로 가장 작은 배열이 만들어지도록 그룹을 나누고 키를 할당하기를 원한다.

입력의 첫째 줄에는 두 정수 n와 k (1 ≤ n ≤ $10^5$, 1 ≤ k ≤ 256)가 주어지며, 각각 이미지의 픽셀 수와 그룹의 최대 크기를 나타낸다.

둘째 줄에는 n개의 정수 $p_1$, $p_2$, ..., $p_n$ (0 ≤ $p_i$ ≤ 255)가 주어지며, 여기서 $p_i$는 i-th 픽셀의 색상이다.

Posterization 필터를 적용한 뒤의 이미지를 나타내는, 가능한 배열 중 사전순으로 가장 작은 배열인 공백으로 구분된 n개의 정수를 출력한다.

첫 번째 예제에서 색상을 그룹으로 묶고 키를 할당하는 가능한 방법 중 하나는 다음과 같다.

색상 2는 그룹 키가 0인 그룹 $[0,2]$에 속한다.

색상 14는 그룹 키가 12인 그룹 $[12,14]$에 속한다.

색상 3과 4는 그룹 키가 3인 그룹 $[3, 5]$에 속한다.

다른 그룹들은 결과에 영향을 주지 않으므로 여기에 나열하지 않았다.