Blood Pressure Game

Problem Description

Gugulu, a JBer, who was an ACMer two years ago, comes to HDOJ taking part in the 2020 Multi-University Training Contest again. However, every time when Gugulu came to regional, he always got an Iron Medal and would consider this competition JB-like. To release his pain, Gugulu would go to the Shanghai Disneyland Park to have fun in taking the Roller Coaster. Gugulu loves the feeling with high-level blood pressure so much which makes him feel like a happy flappy bird who forgets all the Wrong Answers and Time Limit Exceededs etc. We can regard the path of the Roller Coaster as a list of turning points with different heights which can be represented as an array {$a_1,a_2,a_3,\dots,a_n$} of size $n$, and Gugulu's final blood pressure after the game of the Roller Coaster is counted as the sum of all absolute values of the differences between the $n - 1$ pairs of adjacent array numbers, i.e. $\sum_{i=1}^{n-1} \left| a_i - a_{i+1} \right|$. Gugulu always got Iron Medals and is always getting Iron Medals, which makes him keep taking the Roller Coaster over and over again. However, as playing more games, his threshold on the value of blood pressure which can make himself happy is keeping increasing. As a result, the Roller Coaster of Shanghai Disneyland Park can hardly meet Gugulu's needs anymore. Therefore, Gugulu decides to rearrange the array {$a_1,a_2,a_3,\dots,a_n$} in any order to make his blood pressure as high as possible. Moreover, he wants to know the largest $k$ distinct possible values of blood pressure that can be achieved and the number of the corresponding permutations. You, another JBer, are sure that Gugulu is clever enough to get the highest blood pressure as he can. It is very important for you to calculate the correct answer to make an appointment with a proper cardiologist in advance to save Gugulu's life. You must solve this problem! Gugulu's blood pressure is becoming out of control!

Input

The first line of the input contains the number of test cases, $T$ ($1 \leq T \leq 5$). $T$ test cases follow. For each test case, the first line contains two integers, $n$ ($2 \leq n \leq 600$) and $k$ ($1 \leq k \leq 20$). Then, in second line, there are $n$ integers {$a_1,a_2,a_3,\dots,a_n$} ($1 \leq a_i \leq 10^6$), denoting the $n$ original Roller Coaster turning points. As it is an exciting Roller Coaster, it is guaranteed that all $n$ integers in the array are pairwise different.

Output

For each test case, output $k$ lines. For the $i$-th ($1\leq i\leq k$) line, print two numbers $w_i$ and $c_i$, where $w_i$ denotes the $i$-th largest possible value of blood pressure that can be achieved and $c_i$ denotes the number of corresponding permutations modulo $10^9+7$. Note that when the $i$-th largest possible value doesn't exist, print "$\texttt{-1}$" instead.

Sample Input

1
4 8
1 3 7 9

Sample Output

20 2
18 4
16 2
14 8
12 2
10 4
8 2
-1

Source

2020 Multi-University Training Contest 2