| Codeforces Round 134 (Div. 2) |
|---|
| Закончено |
Маленький Болек нашел картину, на которой изображены n горных вершин. Изображение n горных вершин представляет собой незамкнутую ломаную, состоящую из 2n отрезков. Отрезки проходят через 2n + 1 точек с координатами (1, y1), (2, y2), ..., (2n + 1, y2n + 1), i-й отрезок соединяет точку (i, yi) и точку (i + 1, yi + 1). Для любого четного i (2 ≤ i ≤ 2n) выполняется yi - 1 < yi и yi > yi + 1.
Назовем вершину ломаной с четной x координатой горным пиком.
На рисунке слева изображена изначальная картина, на рисунке справа изображена картина после действий Болека. Затронутые пики помечены красным, k = 2. Болек решил похулиганить. Он выбрал ровно k горных пиков, стер отрезки проходящие через эти пики, увеличил высоту каждого выбранного пика на единицу (то есть увеличил координату y соответствующих точек), а затем дорисовал недостающие отрезки так, чтобы получился новый рисунок горных вершин. Обозначим точки, через которые проходит новая ломаная на рисунке, который изменил Болек, через (1, r1), (2, r2), ..., (2n + 1, r2n + 1).
Вам задан полученный Болеком рисунок. Восстановите исходный рисунок.
В первой строке записаны два целых числа через пробел n и k (1 ≤ k ≤ n ≤ 100). В следующей строке записаны 2n + 1 целых чисел через пробел r1, r2, ..., r2n + 1 (0 ≤ ri ≤ 100) — y-координаты вершин ломаной на рисунке Болека.
Гарантируется, что данный рисунок можно получить описанными действиями из некоторого рисунка горных вершин.
Выведите 2n + 1 целых чисел y1, y2, ..., y2n + 1 — y-координаты вершин ломаной на первоначальном рисунке. Если ответов несколько выведите любой.
3 2
0 5 3 5 1 5 2
0 5 3 4 1 4 2
1 1
0 2 0
0 1 0
