Mendelian Genetics

The Austrian monk Gregor Mendel (1822–1884) is regarded as the founding father of genetics for his pioneering theory of genotypic inheritance. In this problem you help Mendel speed up his pea-hybridization experiments.

Consider only one feature of the peas: their size. Starting from $n$ initial types, each with a size, hybridizing them pairwise yields $n^2$ hybrid types after one generation. Mendel wants larger peas, but he can afford to grow only $n$ of the $n^2$ candidates, so he must pick the $n$ most promising ones.

Without knowing the hidden genotypes, he estimates the size of the hybrid of two parents of sizes $x$ and $y$ with the formula

$$\left\lceil \frac{x + y}{2} \right\rceil$$

For example, if the two parents have sizes $5$ and $2$, the hybrid is estimated to have size $\lceil 7/2 \rceil = 4$.

Find the largest $n$ values in this $n \times n$ matrix of pairwise combinations. A type may also be combined with itself, i.e. the diagonal entries are included.

The first line contains the number $K$ of data sets. Then follow $K$ data sets, each of the following form:

• The first line contains an integer $n$ ($1 \le n \le 10000$), the number of initial types.
• The second line contains $n$ positive integers, the sizes of the initial types.

For each data set, output Data Set x: on a line by itself, where $x$ is its number (starting from $1$). On the next line output the largest $n$ numbers from the $n \times n$ matrix of combinations, sorted in descending order and separated by single spaces. Separate consecutive data sets with a single blank line.