题目背景

Source: AMPPZ 2019.

题目描述

Franek 有一项任务：记住序列 $(1, 2, \ldots, n)$ 的一个排列 $P$。然而，这对他来说太无聊了。于是，他发明了一种全新的、奇妙的方式来压缩这些数字：他选取了一个较小的整数 $k$，并只记住了 $P$ 中所有连续的 $k$ 长度片段的和。换句话说，Franek 现在有一个序列 $S = (S_1, S_2, \ldots, S_{n-k+1})$，其中：

• $S_1 = P_1 + P_2 + \ldots + P_k$，
• $S_2 = P_2 + P_3 + \ldots + P_{k+1}$，
• $\ldots$
• $S_{n-k+1} = P_{n-k+1} + P_{n-k+2} + \ldots + P_n$。

然而，这种方法很快被证明并不那么奇妙。首先，Franek 惊恐地发现，有时会有多个排列压缩成相同的序列。此外，他现在甚至不确定自己是否正确地记住了压缩后的序列——初始排列可能已经永远丢失了！

给定一个压缩序列 $S$，帮助 Franek 找到所有与 $S$ 对应的排列 $P$。

输入格式

本题单个测试点内有多组测试数据。

第一行输入包含测试数据的数量 $z$（$1 \le z \le 1000$）。接下来是每组测试数据，格式如下：

每组测试数据的第一行包含排列的长度 $n$ 和 Franek 选择的小整数 $k$（$2 \le n \le 25000$；$2 \le k \le \min(n, 6)$）。第二行包含 $n - k + 1$ 个整数：压缩序列 $S$ 的元素（$1 \le S_i \le 1\,000\,000$）。

所有测试数据中排列的总长度不超过 250, 000。

输出格式

对于每组测试数据，首先输出与给定序列 $S$ 对应的排列的数量 $c$。接下来的 $c$ 行，按字典序输出这些排列。每个排列应在一行内用 $n$ 个整数表示，用空格分隔。

假设在给定的测试数据中，$c$ 永远不会超过 1000。

2
5 3
8 10 12
5 3
10 10 10

2
1 2 5 3 4
2 1 5 4 3
0