Description

Gugulu 是一名 JBer，两年前曾是一名 ACMer，如今又来到 HDOJ 参加 2020 多校联合训练赛。然而，每次参加区域赛，Gugulu 总是拿到铁牌，并认为这种比赛很 JB。为了释放痛苦，Gugulu 会去上海迪士尼乐园坐过山车找乐子。Gugulu 非常喜欢血压飙升的感觉，这让他觉得自己像一只快乐的小鸟，忘掉所有的 Wrong Answer 和 Time Limit Exceeded 等等。 我们可以把过山车的轨道看作一串高度各不相同的转折点，用一个长度为 $n$ 的数组 $\{a_1, a_2, a_3, \dots, a_n\}$ 表示，而 Gugulu 坐完过山车后的最终血压值，等于数组中 $n-1$ 对相邻元素之差的绝对值之和，即 $\sum_{i=1}^{n-1} \left| a_i - a_{i+1} \right|$。

Gugulu 过去总是拿铁牌，未来也总是拿铁牌，这让他一遍又一遍地去坐过山车。然而，随着玩的次数增多，能让他快乐的血压阈值也在不断升高。结果，上海迪士尼乐园的过山车渐渐无法满足 Gugulu 的需求了。

因此，Gugulu 决定把数组 $\{a_1, a_2, a_3, \dots, a_n\}$ 按任意顺序重新排列，使他的血压值尽可能高。此外，他还想知道能够达到的最大的 $k$ 个不同的血压值，以及达到每个血压值对应的排列数量。

而你，另一名 JBer，确信 Gugulu 足够聪明，能拿到他能达到的最高血压。为了提前预约一位合适的心脏科医生来拯救 Gugulu 的生命，计算出正确答案对你来说至关重要。你必须解决这道题！Gugulu 的血压快要失控了！

Format

Input

输入的第一行包含测试数据的组数 $T$（$1 \leq T \leq 5$）。接下来是 $T$ 组测试数据。

对于每组测试数据，第一行包含两个整数 $n$（$2 \leq n \leq 600$）和 $k$（$1 \leq k \leq 20$）。

第二行包含 $n$ 个整数 $\{a_1, a_2, a_3, \dots, a_n\}$（$1 \leq a_i \leq 10^6$），表示过山车的 $n$ 个原始转折点。由于这是一次刺激的过山车之旅，保证数组中的 $n$ 个整数两两不同。

Output

对于每组测试数据，输出 $k$ 行。第 $i$ 行（$1 \leq i \leq k$）输出两个数 $w_i$ 和 $c_i$，其中 $w_i$ 表示能够达到的第 $i$ 大血压值，$c_i$ 表示达到该血压值的排列数量（对 $10^9+7$ 取模）。注意，当第 $i$ 大的血压值不存在时，输出 $\texttt{-1}$。

Samples

1
4 8
1 3 7 9

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

Source

2020 Multi-University Training Contest 2