要求一个排列的相邻差的绝对值之和 $\sum \vert{}a_{p_i} - a_{p_{i+1}}\vert{}$，直接做非常困难。

我们可以利用一个核心数学性质：$\vert{}x - y\vert{} = \max(x, y) - \min(x, y)$。

如果我们把排列中的每一个元素看作图上的节点，相邻的元素连一条边，那么每个元素：

• 作为波峰（比两边都大），会被加 $2$ 次（系数为 $+2$）。
• 作为波谷（比两边都小），会被减 $2$ 次（系数为 $-2$）。
• 作为单调区间中间的数（一边大一边小），会被加 $1$ 次减 $1$ 次（系数为 $0$）。
• 如果元素在排列的边界（即 $p_1$ 或 $p_n$），它只与一个数相邻，因此它的系数只能是 $+1$ 或 $-1$。

为了方便确定每个数的系数，我们先将数组 $a$ 从小到大排序。按从小到大的顺序逐个将 $a_i$ 插入到目标排列中。

因为我们是按顺序插入，当前插入的数 $a_i$ 一定比之前所有的数都大。

• 如果 $a_i$ 作为新连通块独立存在，它相对于未来的邻居是个波谷，系数为 $-2$（或边界的 $-1$）。
• 如果 $a_i$ 依附于某个已有连通块的边缘，它是单调的中间节点，系数为 $0$（或边界的 $+1$）。
• 如果 $a_i$ 将两个已有连通块合并成一个，它是两边的波峰，系数为 $+2$。

我们定义状态 $f[i][j][e]$ 表示：当前已经处理了前 $i$ 个数，当前这些数构成了 $j$ 个连通块，当前已经占据了排列边界的数量（$e \in \{0, 1, 2\}$，即排列的最左端和最右端是否已被填充）。

因为题目要求前 $k$ 大的不同取值及其方案数，$f[i][j][e]$ 内部不只存一个数，而是存一个大小最多为 $k$ 的降序序列，里面每个元素是 pair<和, 方案数>。

假设当前考虑到第 $i$ 个数 $v = a_i$，我们有 $j$ 个连通块和 $e$ 个边界，可以进行以下 $5$ 种操作（乘法原理计算方案数）：

1. 新建内部连通块：在现有的 $j$ 个连通块周围（共 $j+1$ 个空隙，排除已被占用的 $e$ 个边界）新建。系数：$-2v$； 方案数：$j + 1 - e$； 目标状态：$[j+1][e]$。
2. 新建边界连通块：直接放在排列两端的空边界上。系数：$-v$； 方案数：$2 - e$； 目标状态：$[j+1][e+1]$。
3. 加入已有连通块的内部端点：添加到某个连通块未靠边界的端点（共 $2j - e$ 个可用端点）。系数：$0$； 方案数：$2j - e$； 目标状态：$[j][e]$。
4. 加入已有连通块并靠边界：将其一端接在原连通块上，另一端顶到排列的空边界上。系数：$+v$； 方案数：$2 - e$； 目标状态：$[j][e+1]$ (前提是 $j>0$)。
5. 合并两个连通块：将 $a_i$ 放在两个连通块中间，把它们连起来。系数：$+2v$； 方案数：$j - 1$； 目标状态：$[j-1][e]$。

最终答案存在于处理完 $n$ 个数，合并为 $1$ 个连通块且占据 $2$ 个边界的状态 $f[n][1][2]$ 中。

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

#define N 605
#define M 1000000007
#define LL long long
#define PLL pair<LL, LL>

int n, k;
LL a[N];
vector<PLL> f[N][N][3]; // f[当前处理的元素个数][连通块数][边界数]

// 将 src 合并到 tar 中，保留前 k 大，同时累加权值和方案数
void merge(vector<PLL> &tar, vector<PLL> &src, LL w, LL cnt) {
    if (!cnt || !src.size()) return;
    vector<PLL> nxt;
    int i = 0, j = 0;
    while (nxt.size() < k && (i < tar.size() || j < src.size())) {
        if (i < tar.size() && j < src.size()) {
            LL v = src[j].first + w;
            if (tar[i].first == v) {
                nxt.push_back({tar[i].first, (tar[i].second + src[j].second * cnt) % M});
                i++;
                j++;
            } else if (tar[i].first > v) {
                nxt.push_back(tar[i]);
                i++;
            } else {
                nxt.push_back({v, (src[j].second * cnt) % M});
                j++;
            }
        } else if (i < tar.size()) {
            nxt.push_back(tar[i]);
            i++;
        } else {
            LL v = src[j].first + w;
            nxt.push_back({v, (src[j].second * cnt) % M});
            j++;
        }
    }
    tar = nxt;
}

int main() {
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    if (n == 1) {
        printf("0 1\n");
        for (int i = 1; i < k; i++) printf("-1 -1\n");
        return 0;
    }
    // 按从小到大排序，保证当前插入的数一定比之前所有的数都大
    sort(a + 1, a + n + 1);
    // 初始状态：处理了 0 个数，0 个连通块，0 个边界占用
    f[0][0][0] = {{0, 1}};
    for (int i = 1; i <= n; i++) {
        // 遍历上一层 (i - 1) 的所有合法状态
        for (int j = 0; j <= i - 1; j++) {
            for (int e = 0; e <= 2; e++) {
                if (!f[i - 1][j][e].size()) continue;
                LL v = a[i];
                // 新建一个不靠边界的连通块
                if (j + 1 - e > 0)
                    merge(f[i][j + 1][e], f[i - 1][j][e], -2LL * v, j + 1 - e);
                // 新建一个靠边界的连通块
                if (2 - e > 0)
                    merge(f[i][j + 1][e + 1], f[i - 1][j][e], -1LL * v, 2 - e);
                // 添加到已有连通块的非边界端
                if (2 * j - e > 0)
                    merge(f[i][j][e], f[i - 1][j][e], 0, 2 * j - e);
                // 添加到已有连通块，并将这一端顶在排列的空边界上
                if (j > 0 && 2 - e > 0)
                    merge(f[i][j][e + 1], f[i - 1][j][e], v, 2 - e);
                // 将当前数作为波峰，合并两个已有的连通块
                if (j >= 2)
                    merge(f[i][j - 1][e], f[i - 1][j][e], 2LL * v, j - 1);
            }
        }
    }
    // 最终状态为：处理完 n 个数，合并成 1 个连通块，且占据 2 个边界
    vector<PLL> ans = f[n][1][2];
    for (int i = 0; i < k; i++) {
        if (i < ans.size()) {
            printf("%lld %lld\n", ans[i].first, ans[i].second);
        } else {
            printf("-1 -1\n");
        }
    }
    return 0;
}