问题描述

恰逢 H 国国庆，国王邀请 n （ n 是奇数 ）位大臣来玩一个游戏。首先，他让大臣们围成一圈，然后按顺时针方向给大臣依次编号为 1 、2、……、n 号。1 号大臣和 2 号大臣相邻，2 号大臣和 3 号大臣相邻，……，n 号大臣和 1 号大臣相邻。

每两个相邻的大臣之间有一个篮子。1 号大臣和 2 号大臣之间的篮子称为 1 号篮子，2 号大臣和 3 号大臣之间的篮子称为 2 号篮子，……，n 号大臣和 1 号大臣之间的篮子称为 n 号篮子。

初始时，所有的篮子都是空的。

国王给每个大臣分发了若干克金子。每个大臣分到的金子克数都是非负整数。可能有的大臣没有被分发金子，即国王给他分发了 0 克金子。

每个大臣会把分到的金子平均放到两侧的篮子中。

现在给出每个篮子中最终的金子重量，i 号篮子中的金子重量为 Si 克。

问：国王给每个大臣分发了多少克金子？

输入格式

多组数据。每组数据：

• 第一行：包含一个整数 n
• 第二行：包含 n 个整数 Si，依次表示最终 1、2、……、n 号篮子中的金子重量。

当读取到 n = 0 时表示输入结束。

输出格式

若干行，每组数据的答案占一行。对于每组数据：

• 如果无解，则输出 -1
• 如果有唯一解，则输出一行 n 个整数，依次表示国王分发给 1、2、……、n 号大臣的金子重量。
• 如果有多组解，则输出字典序最小的一组解，包含 n 个整数，依次表示国王分发给 1、2、……、n 号大臣的金子重量。

输入样例

3
1 1 2
3
2 4 3
3
1 2 100
0

输出样例

2 0 2
1 3 5
-1

数据范围

保证所有测试点的数据组数不超过 10 组，每组数据的 n 均为奇数。

30% 的数据：$2 < n < 10^3, 0 ≤ Si ≤ 10^3$

100% 的数据：$2 < n < 10^6, 0 ≤ Si ≤ 10^9$