CF2252D.Array Replacement

You are given an array $a$ of length $n$.

You can perform the following operation any number of times (possibly zero):

• Choose an index $i$ ($2 \le i \le n - 1$) such that $a_{i - 1}$ and $a_{i + 1}$ have the same parity.
• Replace $a_i$ with $a_{i - 1} - a_i + a_{i + 1}$.

Find the lexicographically smallest array that can be obtained after any number of operations.

A sequence $x$ is lexicographically smaller than a sequence $y$ of the same length if and only if, in the first position where $x$ and $y$ differ, the element in $x$ is strictly smaller than the corresponding element in $y$.

给你一个长度为 $n$ 的数组 $a$。

你可以执行以下操作任意次（包括零次）：

• 选择一个下标 $i$（满足 $2 \le i \le n - 1$），使得 $a_{i - 1}$ 与 $a_{i + 1}$ 具有相同的奇偶性；
• 将 $a_i$ 替换为 $a_{i - 1} - a_i + a_{i + 1}$。

求经过任意次操作后能得到的字典序最小的数组。

当且仅当在 $x$ 与 $y$ 首次出现不同元素的位置上，$x$ 中该位置的元素严格小于 $y$ 中对应位置的元素时，称序列 $x$ 的字典序小于同长度的序列 $y$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($3 \le n \le 2 \cdot 10^5$) — the length of the array $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$3 \le n \le 2 \cdot 10^5$）——数组 $a$ 的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-10^9 \le a_i \le 10^9$）。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

For each test case, output $n$ integers — the lexicographically smallest array that can be obtained.

对于每个测试用例，输出 $n$ 个整数——所能得到的字典序最小的数组。

In the second test case, the initial array is $[1, 2, 3]$. The only valid index to choose is $i = 2$, because $a_1 = 1$ and $a_3 = 3$ have the same parity. Replacing $a_2$ with $1 - 2 + 3 = 2$ leaves the array unchanged. Thus, the minimal array is $[1, 2, 3]$.

In the third test case, the initial array is $[10, 10, 8, 4]$. We can perform the following sequence of operations:

• Choose $i = 2$ ($a_1 = 10$ and $a_3 = 8$ are both even). Replace $a_2$ with $10 - 10 + 8 = 8$. The array becomes $[10, 8, 8, 4]$.
• Choose $i = 3$ ($a_2 = 8$ and $a_4 = 4$ are both even). Replace $a_3$ with $8 - 8 + 4 = 4$. The array becomes $[10, 8, 4, 4]$.
• Choose $i = 2$ ($a_1 = 10$ and $a_3 = 4$ are both even). Replace $a_2$ with $10 - 8 + 4 = 6$. The array becomes $[10, 6, 4, 4]$.

It can be shown that $[10, 6, 4, 4]$ is the lexicographically smallest array obtainable.

在第二个测试用例中，初始数组为 $[1, 2, 3]$。唯一可选的有效下标是 $i = 2$，因为 $a_1 = 1$ 和 $a_3 = 3$ 具有相同的奇偶性。将 $a_2$ 替换为 $1 - 2 + 3 = 2$ 后，数组保持不变。因此，字典序最小的数组为 $[1, 2, 3]$。

在第三个测试用例中，初始数组为 $[10, 10, 8, 4]$。我们可以执行以下操作序列：

• 选择 $i = 2$（$a_1 = 10$ 和 $a_3 = 8$ 均为偶数）。将 $a_2$ 替换为 $10 - 10 + 8 = 8$，数组变为 $[10, 8, 8, 4]$。
• 选择 $i = 3$（$a_2 = 8$ 和 $a_4 = 4$ 均为偶数）。将 $a_3$ 替换为 $8 - 8 + 4 = 4$，数组变为 $[10, 8, 4, 4]$。
• 选择 $i = 2$（$a_1 = 10$ 和 $a_3 = 4$ 均为偶数）。将 $a_2$ 替换为 $10 - 8 + 4 = 6$，数组变为 $[10, 6, 4, 4]$。

可以证明，$[10, 6, 4, 4]$ 是所能得到的字典序最小的数组。