ZG. Sliding Cost
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array of $$$n$$$ integers. Your task is to calculate for each window of $$$k$$$ elements, from left to right, the minimum total cost of making all elements equal.

You can increase or decrease each element with cost $$$x$$$ where $$$x$$$ is the difference between the new and the original value. The total cost is the sum of such costs.

Input

The first input line contains two integers n and k: the number of elements and the size of the window.

Then there are $$$n$$$ integers $$$x_1,x_2,\dots,x_n$$$: the contents of the array.

Output

Output $$$n−k+1$$$ values: the costs.

Example
Input
8 3
2 4 3 5 8 1 2 1
Output
2 2 5 7 7 1