Вам надано масив із \(n\) цілих чисел. Ваше завдання полягає в тому, щоб обчислити для кожного вікна з \(k\) елементів, зліва направо, мінімальну загальну вартість створення всіх елементів однаковими. Ви можете збільшити або зменшити кожен елемент із вартістю \(x\), де \(x\) — різниця між новим і вихідним значенням. Загальна вартість — це сума таких витрат.

Обмеження

• \(1≤k≤n≤2⋅10^5\)
• \(1≤x_i ​ ≤10^9\)

Формат вхідних даних

Перший рядок містить два цілі числа \(n\) і \(k\): кількість елементів і розмір вікна.

Потім є \(n\) цілих чисел \(x_1 ​ , x_2 ​ ,…, x_n\) ​ : вміст масиву.

Формат вихідних даних

Вихідні дані \(n−k+1\) значень: витрати.

Приклад вхідних даних

8 3
2 4 3 5 8 1 2 1

Приклад вихідних даних

2 2 5 7 7 1