A. Interesting Index
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You're given an array $$$a$$$ of size $$$n$$$.

You can do the following two types of operations any number of times:

  • Rerange the array in any order;
  • Make $$$a_i:=-a_i(1\leq i \leq n)$$$.
An index $$$i(2\leq i \leq n)$$$ is called interesting if and only if $$$(a_1+...+a_{i-1}) \dot (a_1+...+a_i) \leq 0$$$.

Output any array $$$a$$$ after your operations,which maximizes the number of interesting indexes.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The description of the test cases follows.

The first line of each testcase contains a single integer $$$n$$$ ($$$2 \le n \le 2\cdot 10^5$$$).

The second line of each testcase contains $$$n$$$ integers $$$a_1,a_2,\ldots, a_n$$$ ($$$0 \le a_i \lt 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 on a new line — an array $$$a$$$ after your operations,which maximizes the number of interesting indexes.

Example
Input
2
3
2 0 2
4
3 4 5 6
Output
2 -2 0
-4 5 -3 6
Note

Test Case $$$1$$$:

$$$a_1(a_1+a_2)=2*0=0,i=2$$$ is interesting;

$$$(a_1+a_2)(a_1+a_2+a_3)=0*0=0,i=3$$$ is interesting.

The number of interesting indexes is $$$2$$$.It shows that $$$2$$$ is the maximum.

Test Case $$$2$$$:

$$$a_1(a_1+a_2)=-4*1=-4,i=2$$$ is interesting;

$$$(a_1+a_2)(a_1+a_2+a_3)=1*(-2)=-2,i=3$$$ is interesting;

$$$(a_1+a_2+a_3)(a_1+a_2+a_3+a_4)=-2*4=-8,i=4$$$ is interesting.

The number of interesting indexes is $$$3$$$.It shows that $$$3$$$ is the maximum.