Профессор Ибрагим подготовил последнее домашнее задание для его курса алгоритмов. Он хочет, чтобы его студенты написали постеризационный фильтр для изображений.
Этот алгоритм будет тестироваться на массиве целых чисел, в котором \(i\)-е число обозначает цвет \(i\)-го пикселя в изображении. Изображение чёрно-белое, поэтому цвет каждого пикселя будет целым числом между 0 и 255 (включительно).
Для реализации алгоритма фильтра студенты должны разделить чёрно-белую гамму [0, 255] на группы последовательных цветов и выбрать в каждой группе один ключевой цвет. Для сохранения деталей изображения размер каждой группы не может быть больше \(k\) и каждый цвет должен принадлежать ровно одной группе. После этого студенты должны заменить цвет каждого пикселя в массиве на ключевой цвет группы, в которую он входит.
Для лучшего понимания эффекта снизу приведено несколько изображений греющейся на солнце черепахи, к каждому из которых был применён постеризационный фильтр, причём \(k\) для них растёт слева направо.
Для упрощения процесса проверки профессор Ибрагим хочет, чтобы студенты разбили цвета на группы и выбрали ключевые цвета таким образом, что результирующий массив будет лексикографически наименьшим из всех возможных.
Выходные данные
Выведите \(n\) целых чисел, разделённых пробелами — лексикографически наименьший массив, являющийся результатом применения постеризационного фильтра к исходному изображению.
Примечание
Один из возможных методов выбора групп и ключевых цветов для первого примера таков:
Цвет \(2\) принадлежит группе \([0,2]\) с ключевым цветом \(0\).
Цвет \(14\) принадлежит группе \([12,14]\) с ключевым цветом \(12\).
Цвета \(3\) и \(4\) принадлежат группе \([3, 5]\) с ключевым цветом \(3\).
Остальные группы не повлияют на результат, поэтому они не выписаны.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3
2 14 3 4
|
0 12 3 3
|
|
2
|
5 2
0 2 1 255 254
|
0 1 1 254 254
|