该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

置换

题目描述

许老师给乐柠兔一个长度为 $n$ 的整数数组 $a_1,a_2,\ldots,a_n$。

乐柠兔可以进行任意次如下操作，也可以一次都不进行：

选择一个下标 $i$，满足 $2\le i\le n-1$，并且 $a_{i-1}$ 与 $a_{i+1}$ 的奇偶性相同，然后将 $a_i$ 替换为

经过若干次操作后，数组可能变为不同的序列。乐柠兔希望得到其中按字典序最小的数组。

对于两个长度均为 $n$ 的序列 $x$ 与 $y$，若存在位置 $k$，使得对所有 $1\le j<k$ 都有 $x_j=y_j$，且 $x_k<y_k$，则称 $x$ 的字典序小于 $y$。

你需要对每组测试数据求出能够得到的字典序最小数组。

输入格式

第一行包含一个整数 $t$，表示测试用例组数。

接下来依次输入 $t$ 组测试用例。对于每组测试用例：

第一行包含一个整数 $n$，表示数组长度。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示初始数组。

输出格式

对于每组测试用例，输出一行 $n$ 个整数，表示经过任意次合法操作后能够得到的字典序最小数组。

相邻整数之间用一个空格分隔。

样例

样例输入 #1

3
10
100 108 114 118 120 5 7 19 13 11
3
1 2 3
4
10 10 8 4

样例输出 #1

100 102 106 112 120 5 -1 -3 -1 11
1 2 3
10 6 4 4

数据范围与约定

对于 $100\%$ 的数据，保证 $1\le t\le 10^4$，$3\le n\le 2\times 10^5$，$-10^9\le a_i\le 10^9$，且单个输入文件中所有测试用例的 $n$ 之和不超过 $2\times 10^5$。

固定设置 $20$ 个测试点。

• 特殊性质 A：对于每组测试用例，所有 $a_i$ 的奇偶性均相同。
• 特殊性质 B：令 $d_i=a_{i+1}-a_i$，则对所有 $1\le i\le n-2$，$d_i$ 与 $d_{i+1}$ 的奇偶性不同。