D. Beds Building (hard version!)
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the harder version of the problem. In this version you need to pick $$$4\cdot k$$$ indices instead of 4, and the constraints are higher.

Munir is building his new beds from IKAE! He has already dumped all his wood of lengths $$$a_1,a_2,\dots,a_n$$$ on the floor. Now the first step is to build the bed frame.

Each bed frame should consist of two pieces of length $$$x$$$, and two of length $$$y$$$ (possibly with $$$x=y$$$). Unfortunately, IKAE does not have very good quality control, so he finds that he might not have two pairs of wood with the same lengths.

Instead, he tries to build almost perfect bed frames. Specifically, he should pick distinct indices $$$i_1, i_2,\dots,i_{4k}$$$ to minimize the deviation $$${\sum_{i=1}^k{|a_{4i}-a_{4i+1}| + |a_{4i+2}-a_{4i+3}|}}$$$.

Unfortunately he has too many pieces of wood, so he cannot do this by himself. Help him!!

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t\ (1\le t\le 10^4)$$$. The description of the test cases follows.

The first line of each test case contains two integer $$$n, k\ (4\le n\le 5\cdot 10^5, k\le \lfloor \frac{n}{4}\rfloor)$$$ — the number of wood planks Munir has and the number of beds he will build, respectively.

The second line of each test case contains n integers $$$a_1,a_2,\dots,a_n\ (1\le a_i\le 10^{18})$$$ — the lengths of each wood plank.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$5\cdot 10^5$$$.

Output

For each test case, output a single integer: the smallest possible deviation of a bed frame given the wood lengths.

Example
Input
4
4 1
1 2 3 4
8 2
10 20 80 160 320 640 40 999999
5 1
2 1 2 1 2
20 3
56 100 8 19 25 46 18 19 9 15 10 7 11 5 24 5 77 12 99 23
Output
2
999569
0
4