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$数组有多种可能,输出任意一个即可。