CF1512D Corrupted Array
题目描述
给定一个正整数$n$和长度为$n+2$的数组$b$,数组$b$是依据如下算法构造的:
- 随机生成一个含有 $n$ 个元素的原始数组$a$;
- 把数组 $a$ 赋值给数组 $b$,即 $b_i=a_i(1\le i\le n)$;
- 数组 $b$ 的第 $n+1$ 个元素为数组 $a$ 的元素和,即 $b_{n+1}=\sum_{i=1}^na_i$;
- 数组 $b$ 的第 $n+2$ 个元素是个随机整数 $x(1\le x\le10^9)$;
- 打乱 $b$ 数组。
例如,数组 $b=[2,3,7,12,2]$,那么它能够通过如下方式构建:
- $a=[2,2,3]$,且$x=12$;
- $a=[3,2,7]$,且$x=2$。
给定一个$b$数组,请你求出它对应的$a$数组。
输入格式
第一行一个整数$T(1\le T\le10^4)$表示数据组数。
对于每组数据,第一行有一个整数$n(1\le n\le2\cdot10^5)$。
第二行有$n+2$个整数,即$b$数组的值$(1\le b_i\le10^9)$。
保证所有测试数据的$n$之和不超过$2\cdot10^5$。
输出格式
对于每个测试数据,如果找不到对应的数组$a$,请输出$-1$;
如果能找到,就输出$a$数组。
如果$a$数组有多种可能,输出任意一个即可。