问题 1419. -- 两数和

1419: 两数和

时间限制: 1 Sec  内存限制: 256 MB
提交: 305  解决: 30
[提交][状态][讨论版]

题目描述

XDOJ1131的出题人VV,因为不思进取,学完小学数学就得意洋洋,故步自封。于是他天天研究一些加法的问题,比如Fib Sequences,三数和等等。
VV在XDU的ACM实验室遇到了酷爱写special judge的XDOJ1103的出题人DD,他的初中数学学得非常好,竞赛中全省名列前茅。他非常喜欢对各种问题求逆,比如逆函数,反卷积等等,所以他十分看不起只会小学数学的VV,但是VV不服,总是吵架。有一天他们终于忍无可忍,打了起来,为了解决争端,VV给DD出了一道求和,求逆有关的题:
       假如有一个有限的正整数数列{ai},数列的长度是n,从数列中任取两个数相加的和,有n*(n-1)/2个。现在我们已经知道了如果给定数列,那么n*(n-1)/2个和很容易就可以求出来。但是如果只知道n*(n-1)/2个和,求出原数列又如何呢?

DD听完以后,花了1s的时间就说出了做法,VV听到以后立刻觉得自愧不如,于是拜DD为师开始学习初中数学。但是DD认为理论AC不算对,但是他的电脑由于打架的时候被当成了工具打坏了,所以向你求助!

输入

第一行一个正整数T表示数据组数
对于每组数据有两行
第一行一个自然数n表示数列的长度
接下来一行有n*(n-1)/2个正整数si表示任取两个数相加的和。

输出

对于每组数据

若有解,输出一行n个正整数,表示数列的元素,中间以空格隔开,行末无空格。
若无解,则输出Impossible。

由于XDOJ1131的出题人真的十分懒惰,依然没有写SPJ,若有多解,就请输出字典序最小的解吧!

样例输入

2
3
3 5 4
3
10 7 13

样例输出

1 2 3
2 5 8

提示

1<=T<=20


2<=n<=100


1<=si<=231


请使用c语言的标准化读入,cin可能会造成超时的错误。

来源

[提交][状态][讨论版]