P16468 [GKS 2013 #A] Sorting

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}}$ 就是整理后从左到右书的最终价值序列。

### 限制 $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 完成