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

Input

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

Output

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

Note

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.