D. Decomposition
time limit per test
2 seconds
memory limit per test
512 mebibytes
input
standard input
output
standard output

You are given an undirected complete graph with $$$n$$$ vertices, where $$$n$$$ is odd. You need to partition its edge set into $$$k$$$ disjoint simple paths, satisfying that the $$$i$$$-th simple path has length $$$l_i$$$, and each undirected edge is used exactly once. The given lengths $$$l_i$$$ are integers from $$$1$$$ to $$$n - 3$$$.

A complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A simple path is a path where vertices are pairwise distinct. The length of a path is the number of edges in it.

It can be shown that an answer always exists if $$$\displaystyle \sum\limits_{i=1}^k l_i = \frac{n(n-1)}{2}$$$ holds.

Input

The first line contains an integer $$$T$$$ ($$$1 \leq T \leq 10^5$$$), the number of test cases. Then $$$T$$$ test cases follow.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$5 \leq n \leq 1000$$$, $$$1 \leq k \leq \frac{n(n - 1)}{2}$$$, $$$n$$$ is odd), the number of vertices and paths, respectively. The second line contains $$$k$$$ integers $$$l_1, l_2, \ldots, l_k$$$ ($$$1 \le l_i \le n - 3$$$), the required lengths of the paths.

It is guaranteed that $$$\displaystyle \sum\limits_{i = 1}^{k} l_i = \frac{n(n - 1)}{2}$$$ holds for each test case.

It is also guaranteed for the total number of edges over all test cases that $$$\displaystyle \sum \frac{n(n - 1)}{2} \leq 10^6$$$.

Output

For each test case, start by printing one line containing "Case #x:", where $$$x$$$ ($$$1 \leq x \leq T$$$) is the test case number. Then output $$$k$$$ lines. In the $$$i$$$-th of these lines, print $$$l_i + 1$$$ integers denoting the vertices of the $$$i$$$-th path in order of traversal.

If there are multiple answers, print any one of them.

Example
Input
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
Output
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