Кейсі та Ейпріл#12988

Кейсі та Ейпріл

У Кейсі Джонса є масив з елементів. Сьогодні йому цей масив не так уже й подобається, тож він вирішив перетворювати цей масив.

Ейпріл підготувала для Кейсі цікаве медіанне перетворення. Результатом медіанного перетворення масиву є масив розміру такий, що b_i = median(a_{i-1}, a_i, a_{i+1}), де median(x, y, z) — значення, яке стоїть посередині після впорядкування чисел , та за зростанням. Для зручності вважаємо, що a_0=a_n та a_{n+1}=a_1.

Тепер же Кейсі цікаво, який вигляд матиме масив, якщо до нього разів застосувати медіанне перетворення.

Input

В першому рядку задано два цілих числа та .

В другому рядку задано цілих чисел a_i.

3 \le n \le 4 \cdot 10^5,

1 \le k \le 10^9,

1 \le a_i \le 10^9.

Output

Виведіть цілих чисел – масив після перетворень.

Examples

Example

Loading
Loading

Note

Перше перетворення:

  • 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].