Bạn được cho một mảng gồm \(n\) số nguyên. Nhiệm vụ của bạn là: với mỗi đoạn con gồm \(k\) phần tử liêp tiếp, từ trái sang phải, tính tổng chi phí tối thiểu để tất cả các phần tử bằng nhau.

Bạn có thể tăng hoặc giảm từng phần tử với chi phí \(x\), trong đó \(x\) là chênh lệch giữa giá trị mới và giá trị ban đầu. Tổng chi phí của đoạn con là tổng của các chi phí tăng hoặc giảm mỗi phần tử trong đó.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(k\): số lượng phần tử của mảng và kích thước của đoạn con.
• Dòng tiếp theo chứa \(n\) số nguyên \(x_1,x_2,\ldots,x_n\): các phần tử của mảng.

Output

• In ra \(n-k+1\) số: các chi phí.

Constraints

• \(1 \le k \le n \le 2 \cdot 10^5\)
• \(1 \le x_i \le 10^9\)

Example

Sample input

8 3
2 4 3 5 8 1 2 1

2 2 5 7 7 1