Franek 有一项工作：记住序列 $(1, 2, \dots, n)$ 的一个排列 $P$。然而，这太无聊了。于是，他发明了一种奇妙的新方法来压缩这些数字：他取一个较小的整数 $k$，只记住 $P$ 中所有长度为 $k$ 的连续片段的和。换句话说，Franek 现在拥有一个序列 $S = (S_1, S_2, \dots, S_{n-k+1})$，其中： $S_1 = P_1 + P_2 + \dots + P_k$，$S_2 = P_2 + P_3 + \dots + P_{k+1}$，$\dots$，$S_{n-k+1} = P_{n-k+1} + P_{n-k+2} + \dots + P_n$。

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

给定压缩后的序列 $S$，请帮助 Franek 找出所有对应于 $S$ 的排列 $P$。

输入格式

输入的第一行包含测试用例的数量 $z$ ($1 \le z \le 1000$)。接下来是各个测试用例，每个测试用例的格式如下：

第一行包含排列的长度 $n$ 和 Franek 选择的较小整数 $k$ ($2 \le n \le 25\,000$; $2 \le k \le \min(n, 6)$)。第二行包含 $n - k + 1$ 个整数：压缩序列 $S$ 的元素 ($1 \le S_i \le 1\,000\,000$)。

所有测试用例中 $n$ 的总和不超过 $250\,000$。

输出格式

对于每个测试用例，首先输出对应于给定序列 $S$ 的排列数量 $c$。在接下来的 $c$ 行中，按字典序输出这些排列。每个排列应以 $n$ 个整数的形式在一行中给出，并用空格分隔。

假设对于给定的测试用例，$c$ 永远不会超过 $1000$。

样例

输入 1

2
5 3
8 10 12
5 3
10 10 10

输出 1

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