当前没有测试数据。

题目描述

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

你可以执行任意次（可以为 0 次）如下操作：

• 选择下标 $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$）——数组 $a$ 的长度。

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

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

输出格式

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

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

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

说明

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

原题链接

原题链接