CF2252D Array Replacement

给定长为 $ 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 $ 中的值要小。

每组输入数据包含多组测试用例。第一行一个整数 $ t $（$ 1 \le t \le 10^4 $）表示测试用例组数。每组用例的组成如下： 第一行一个整数 $ n $（$ 3 \le n \le 2 \cdot 10^5 $），表示序列长度。 第二行 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $（$ -10^9 \le a_i \le 10^9 $）。 保证每组输入数据中，所有测试用例 $ n $ 的总和不超过 $ 2 \cdot 10^5 $。

一行 $ n $ 个整数表示经过若干次操作后可以得到的字典序最小的序列。

在样例的第二组数据中，初始序列为 $ [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] $ 是可以得到字典序最小的序列。