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

Limits: 7 sec., 512 MiB

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

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

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

Input

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

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

Output

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

Constraints

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

\(1 \le k \le 10^9\),

\(1 \le a_i \le 10^9\).

Samples

Input (stdin) сopy	Output (stdout) сopy
7 2 4 7 47 14 17 11 9	7 7 14 14 14 11 9

Notes

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

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