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