给定一个具有 $n$ 个顶点的无向完全图，其中 $n$ 为奇数。你需要将其边集划分为 $k$ 条不相交的简单路径，满足第 $i$ 条简单路径的长度为 $l_i$，且每条无向边恰好被使用一次。给定的长度 $l_i$ 是 $1$ 到 $n-3$ 之间的整数。

完全图是一个简单的无向图，其中每对不同的顶点都由一条唯一的边连接。简单路径是指顶点互不相同的路径。路径的长度为其包含的边数。

可以证明，如果满足 $\sum_{i=1}^{k} l_i = \frac{n(n-1)}{2}$，则答案总是存在的。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试用例的数量。接下来是 $T$ 个测试用例。

每个测试用例的第一行包含两个整数 $n$ 和 $k$ ($5 \le n \le 1000, 1 \le k \le \frac{n(n-1)}{2}, n$ 为奇数)，分别表示顶点数和路径数。第二行包含 $k$ 个整数 $l_1, l_2, \dots, l_k$ ($1 \le l_i \le n-3$)，表示路径所需的长度。

保证对于每个测试用例，$\sum_{i=1}^{k} l_i = \frac{n(n-1)}{2}$ 成立。

同时保证所有测试用例的边数总和满足 $\sum \frac{n(n-1)}{2} \le 10^6$。

输出格式

对于每个测试用例，首先输出一行 “Case #x:”，其中 $x$ ($1 \le x \le T$) 是测试用例编号。然后输出 $k$ 行。在第 $i$ 行中，输出 $l_i + 1$ 个整数，表示第 $i$ 条路径遍历时的顶点序列。

如果存在多种答案，输出其中任意一种即可。

样例

样例输入 1

3
5 6
2 1 1 2 2 2
7 8
1 1 4 3 4 1 3 4
5 10
1 1 1 1 1 1 1 1 1 1

样例输出 1

Case #1:
5 4 2
2 3
5 1
2 1 4
3 5 2
1 3 4
Case #2:
6 7
1 3
6 5 1 2 3
7 1 4 2
1 6 4 7 5
7 3
2 6 3 5
3 4 5 2 7
Case #3:
5 3
5 2
4 3
1 5
1 3
2 3
4 2
4 1
1 2
4 5