5.4 Color Ball Problem

Score: 50pts

Time Limit: 1.00 sec

In a charming village filled with friendly creatures, there was an exciting challenge afoot. Imagine there were colorful balls with numbers inside them, and they wanted to make all these numbers the same in groups of a certain size.

To make this happen, they could change a ball's number by adding or subtracting a certain amount, but doing so came with a cost. The cost was how much they had to change the number to make it match the others.

So, our friendly villagers set out to solve this puzzle. They moved a special window across the row of balls and, at each step, tried to figure out the cheapest way to make all the balls in that window have the same number.

Sometimes it was easy, and they didn't have to do much magic. Other times, it was more challenging, and they had to be clever and use their magic carefully.

But no matter how tough it got, they didn't give up. They loved the thrill of solving the puzzle and discovering new tricks to make the numbers match without spending too much magic.

And in the end, this village became known for its clever villagers who could make numbers dance and sing together with just a bit of magic, showing that even math could be a magical adventure!

To make this happen, they could change a ball's number by adding or subtracting a certain amount, but doing so came with a cost. The cost was how much they had to change the number to make it match the others.

So, our friendly villagers set out to solve this puzzle. They moved a special window across the row of balls and, at each step, tried to figure out the cheapest way to make all the balls in that window have the same number.

Sometimes it was easy, and they didn't have to do much magic. Other times, it was more challenging, and they had to be clever and use their magic carefully.

But no matter how tough it got, they didn't give up. They loved the thrill of solving the puzzle and discovering new tricks to make the numbers match without spending too much magic.

And in the end, this village became known for its clever villagers who could make numbers dance and sing together with just a bit of magic, showing that even math could be a magical adventure!

Constraints

1≤k≤n≤ 2*10^5

1≤xi≤10^9

1≤xi≤10^9

Input Format

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

Then there are n integers x1,x2,…,xn : the numbers inside the ball.

Then there are n integers x1,x2,…,xn : the numbers inside the ball.

Output Format

Output n−k+1 values: the costs.

Example 1

Input:

8 3

2 4 3 5 8 1 2 1

Output:

2 2 5 7 7 1

Explanation:

This Example is self explanatory

8 3

2 4 3 5 8 1 2 1

Output:

2 2 5 7 7 1

Explanation:

This Example is self explanatory