Description

Given $N$ and a non-negative integer sequence $a_1,a_2,\dots,a_N$.

Please find any integer sequence $b_1,b_2,\dots,b_N$ such that $\sum |b_i|\neq 0$, $|b_i|\le 1$, and $\sum a_i b_i = 0$.

Input Format

The first line contains a positive integer $T$. Then follow $T$ test cases.

Each test case consists of two lines. The first line contains a positive integer $N$, and the next line contains $N$ non-negative integers $a_1,a_2,\dots,a_N$.

Output Format

Output $T$ lines. The $T$-th line should output the sequence $b$ for the corresponding test case.

If there is no solution, output $-1$.

2
5
1 1 2 60 60
4
100 101 100 102

1 1 -1 1 -1
1 0 -1 0

Hint

This sample does not satisfy the constraint $5000\le N$.

This problem uses bundled tests.

• Subtask 1 (50 pts): $10^5\le N$.
• Subtask 2 (50 pts): no special constraints.

Constraints for $100\%$ of the testdata: $1\le T\le 20$, $5000\le N\le\frac{10^5}{T}$, $0\le a_i\le 10^{18}$. The testdata is guaranteed to be randomly generated.

Translated by ChatGPT 5