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 $ .

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 $ .

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

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.