환상적인 압축

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$에 대응하는 모든 순열 $P$를 찾아라.

첫 줄에 테스트 케이스의 수 $z$ ($1 \le z \le 1000$)가 주어진다. 각 테스트 케이스는 다음 형식으로 주어진다.

테스트 케이스의 첫 줄에는 순열의 길이 $n$과 Franek이 정한 작은 정수 $k$가 주어진다 ($2 \le n \le 25\,000$; $2 \le k \le \min(n, 6)$). 둘째 줄에는 압축 수열 $S$의 원소 $n - k + 1$개가 주어진다 ($1 \le S_i \le 1\,000\,000$).

모든 테스트 케이스의 순열 길이 합은 $250\,000$을 넘지 않는다.

각 테스트 케이스마다 주어진 수열 $S$에 대응하는 순열의 개수 $c$를 먼저 출력한다. 이어서 $c$개의 순열을 사전순으로, 한 줄에 하나씩 $n$개의 정수를 공백으로 구분해 출력한다.

주어진 테스트에서 $c$는 $1000$을 넘지 않는다고 가정한다.