550. Sliding Cost

0

Hard

Given an array of n integers, the task is to calculate the minimum total cost of making all elements equal for each window of k elements, moving from left to right.
Each element can be increased or decreased with a cost x, where x is the difference between the new and original value. The total cost is the sum of these costs.

Input Format

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

Then, there are n integers x1, x2, ..., xn, representing the contents of the array.

Then, there are n integers x1, x2, ..., xn, representing the contents of the array.

Output Format

Output n-k+1 values, representing the costs.

Example

Input

8 3
2 4 3 5 8 1 2 1

Output

2 2 5 7 7 1

Constraints

1≤ k ≤ n ≤ 2⋅10

1≤ x[i] ≤10

^{5}1≤ x[i] ≤10

^{9}Loading...

View Submissions

Console