测试数据来自 system/1928

描述

后来，我又一次和木姑娘分处两地了。

那段时间，我见不到她，只能给她去电话。但是她白天有课，晚上还有晚自习，很是忙碌。

有时候打电话过去，她已经睡下了。有时候打电话过去，她却还在晚自习。只能在她恰好快要睡下的时候去电话，才能聊几句。

后来我摸清楚了她的睡觉时间，大概以n天为周期。之后我便估计出来了相邻三天的平均睡觉时间。

如果记t[0],t[1],...,t[n-1]是连续n天开始睡觉的时间，t[i]为整数(可能为负值)，那么我就可以得到另外一个序列b[0],b[1],...,b[n-1]。

其中：b[0] = t[n-1]+t[0]+t[1]，b[1] = t[0]+t[1]+t[2]，依次类推，b[n-1] = t[n-2]+t[n-1]+t[0]。

现在我希望利用已知的信息，去推算出木姑娘每一天是什么时候开始睡觉的。这样是不是就可以每天都听到她的声音了呢？

格式

输入格式

输入第一行n(3<=n<=1000000)

第二行输入n个正整数b[0],...,b[n-1]

输出格式

若存在可能的t0],...,t[n-1]，则以一行输出

若有多组可行方案，输出字典序最小的一组

否则输出-1

样例1

样例输入1

4
3 3 3 3

样例输出1

1 1 1 1 

样例2

样例输入2

3
3 3 4

样例输出2

-1

限制

40%的数据，n<=4000.
70%的数据，n<=100000.
100%的数据，n<=1000000.
对于任意i，满足3<=b[i]<=1000000000