У Кейсі Джонса є масив з елементів. Сьогодні йому цей масив не так уже й подобається, тож він вирішив перетворювати цей масив.
Ейпріл підготувала для Кейсі цікаве медіанне перетворення. Результатом медіанного перетворення масиву є масив розміру такий, що b_i = median(a_{i-1}, a_i, a_{i+1}), де median(x, y, z) — значення, яке стоїть посередині після впорядкування чисел , та за зростанням. Для зручності вважаємо, що a_0=a_n та a_{n+1}=a_1.
Тепер же Кейсі цікаво, який вигляд матиме масив, якщо до нього разів застосувати медіанне перетворення.
В першому рядку задано два цілих числа та .
В другому рядку задано цілих чисел a_i.
3 \le n \le 4 \cdot 10^5,
1 \le k \le 10^9,
1 \le a_i \le 10^9.
Виведіть цілих чисел – масив після перетворень.
Приклад
Перше перетворення:
b_1 = median(9, 4, 7) = 7;
b_2 = median(4, 7, 47) = 7;
b_3 = median(7, 47, 14) = 14;
b_4 = median(47, 14, 17) = 17;
b_5 = median(14, 17, 11) = 14;
b_6 = median(17, 11, 9) = 11;
b_7 = median(11, 9, 4) = 9.
Отже після першого перетворення масив рівний [7, 7, 14, 17, 14, 11, 9].
Після другого перетворення масив стає рівним [7, 7, 14, 14, 14, 11, 9].