题目描述

Alex 和 Bob 是两兄弟，他们都非常喜欢阅读。两人对书的品味大相径庭，因此各自保管自己的书。然而，父亲认为如果能让他们把书放在一起，或许可以促进交流。于是，父亲今天为他们买了一个单排书架，并将两个儿子的所有书随机摆放在上面。他为书架上的每个位置都贴好了标签，标明对应位置上的书的主人（“Alex”或“Bob”）。

不巧的是，Alex 和 Bob 当时外出了，并不知道父亲做了什么。当他们回到家时，才意识到问题所在：他们通常按自己的顺序整理书籍，但现在书架上的书看起来一片混乱。他们必须马上整理！

每本书都有自己的价值，用一个整数表示。价值为奇数的书属于 Alex，价值为偶数的书属于 Bob。Alex 习惯将他的书在书架上从左到右按价值升序排列，而 Bob 则喜欢将他的书从左到右按价值降序排列。

同时，他们不想改变标签的位置，因此在按照各自的规则整理完书籍之后，每本书的主人名字必须与其所在位置的标签一致。

现在问题来了。给定一个长度为 $N$ 的整数序列 $\mathbf{s_0}$, $\mathbf{s_1}$, ..., $\mathbf{s_{N-1}}$，表示当前书架上从左到右每本书的价值。请帮助兄弟俩找出整理后满足上述要求的价值序列。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。每个测试用例的第一行包含一个整数 $N$，表示书架上的书的数量。接下来一行包含 $N$ 个用空格分隔的整数，表示 $\mathbf{s_0}$, $\mathbf{s_1}$, ..., $\mathbf{s_{N-1}}$，即每本书的价值。

输出格式

对于每个测试用例，输出一行形如 Case #X: 的内容，然后依次输出 $\mathbf{t_0}$, $\mathbf{t_1}$, ..., $\mathbf{t_{N-1}}$，用空格分隔。其中 $X$ 是测试用例编号（从 $1$ 开始），而 $\mathbf{t_0}$, $\mathbf{t_1}$, ..., $\mathbf{t_{N-1}}$ 就是整理后从左到右书的最终价值序列。

2
5
5 2 4 3 1
7
-5 -12 87 2 88 20 11

Case #1: 1 4 2 3 5
Case #2: -5 88 11 20 2 -12 87

提示

限制

$1 \le T \le 30$。

测试集 1 - Visible

$1 \le N \le 100$

$-100 \le s_i \le 100$

测试集 2 - Hidden

$1 \le N \le 1000$

$-1000 \le s_i \le 1000$

翻译由 DeepSeek V4 Pro 完成