Волшебные цветы
(Время: 5 сек. Память: 64 Мб Сложность: 77%)
Цветочник Стёпик посадил N волшебных цветков в своём саду. Высадил он их по кругу, и пронумеровал от 1 до N так, что первый и N-й соседи, а для 2 ≤ i ≤ N соседями являются цветы с номерами i и i−1. Каждый i-й цветок имеет свою высоту Hi.
Почему цветы Стёпика волшебные? Потому что к концу дня они меняют свою высоту, а именно высота i-го цветка становится равна наименьшей из высот его соседей. Изменение высот происходит для всех цветков одновременно.
Стёпик собирается уехать на K дней и ему интересно, какими будут высоты цветков к моменту его приезда?
Входные данные
Первая строка входного файла INPUT.TXT содержит два целых числа N и K − количество цветков и количество дней соответственно (3 ≤ N ≤ 5×105; 0 ≤ K ≤ 109).
Во второй строке содержатся N целых чисел Hi (1 ≤ Hi ≤ 109).
Выходные данные
В выходной файл OUTPUT.TXT выведите в одной строке N целых чисел − высоты цветков по истечении K дней.
Примеры
№ | INPUT.TXT | OUTPUT.TXT |
1 | 5 1 3 5 4 1 2 | 2 3 1 2 1 |
2 | 10 2 9 2 6 7 1 4 5 8 3 10 | 3 2 1 2 1 4 1 4 3 2 |
3 | 3 3 3 3 3 | 3 3 3 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|