D. Sum of Differences time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output Let's consider a sequence of integers of length N . A "window" of length K moves along the sequence with a step of 1. In other words, initially, the window shows the first K numbers; on the next step, the window will contain K numbers starting from the second one, and so on until the end of the sequence. It is required to determine F(A) for each position of the window.

The function F(A) − sorts the given sequence of integers in non-decreasing order of elements. In other words, the sequence of integers in the given range will become Ai≤Ai+1 . Then it calculates the sum of the differences between adjacent elements and returns it. Formally, it returns ∑i=2i+k|Ai−Ai−1| .

Example 1 For example: when N=5,K=3,A=[5,2,3,1,4].

First K numbers are [5,2,3] . Then F([5,2,3]) will sort the given range it will be like [2,3,5] . Then sum of differences of the array [2,3,5] will be |3−2|+|5−3|=1+2=3 . Input The first line contains the integer T (1≤T≤100) − the number of test cases.

The first line of each test case contains two integers, N and K (1≤N≤150000,1≤K≤10000,K≤N) – the lengths of the sequence and the "window," respectively. The next line contains N numbers − the sequence itself (1≤Ai≤109) .

It is guaranteed that the sum of N over all test cases does not exceed 150000 .

Output For each testcase, the output should contain N−K+1 integers separated by spaces, representing the F(A) for each position of the "window".