题目描述

给定 $N$ 以及非负整数序列 $a_1,a_2,\dots,a_N$。

请找到 任何 一个整数序列 $b_1,b_2,\dots,b_N$ 满足 $\sum |b_i|\neq 0$，$|b_i|\le 1$，和 $\sum a_ib_i=0$。

输入格式

第一行一个正整数 $T$。接下来 $T$ 组数据。

每一组数据两行，第一行一个正整数 $N$，接下来一行 $N$ 个正整数 $a_1,a_2,\dots,a_N$。

输出格式

输出 $T$ 行，第 $T$ 行输出对应组数据的 $b$ 序列。

如果无解，输出 $-1$。

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

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

提示

本样例不符合题意 $5000\le N$ 的限制。

本题采用捆绑测试。

• Subtask 1（50 pts）：$10^5\le N$
• Subtask 2（50 pts）：无特殊限制。

对于 $100\%$ 的数据：$1\le T\le 20$，$5000\le N\le\frac{10^5}{T}$，$0\le a_i\le 10^{18}$。数据保证随机生成。