D. Corrupted Array

D. Corrupted Array

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a number nn and an array b1,b2,…,bn+2b1,b2,…,bn+2, obtained according to the following algorithm:

• some array a1,a2,…,ana1,a2,…,an was guessed;
• array aa was written to array bb, i.e. bi=aibi=ai (1≤i≤n1≤i≤n);
• The (n+1)(n+1)-th element of the array bb is the sum of the numbers in the array aa, i.e. bn+1=a1+a2+…+anbn+1=a1+a2+…+an;
• The (n+2)(n+2)-th element of the array bb was written some number xx (1≤x≤1091≤x≤109), i.e. bn+2=xbn+2=x; The
• array bb was shuffled.

For example, the array b=[2,3,7,12,2]b=[2,3,7,12,2] it could be obtained in the following ways:

• a=[2,2,3]a=[2,2,3] and x=12x=12;
• a=[3,2,7]a=[3,2,7] and x=2x=2.

For the given array bb, find any array aa that could have been guessed initially.

Input

The first line contains a single integer tt (1≤t≤1041≤t≤104). Then tt test cases follow.

The first line of each test case contains a single integer nn (1≤n≤2⋅1051≤n≤2⋅105).

The second row of each test case contains n+2n+2 integers b1,b2,…,bn+2b1,b2,…,bn+2 (1≤bi≤1091≤bi≤109).

It is guaranteed that the sum of nn over all test cases does not exceed 2⋅1052⋅105.

Output

For each test case, output:

• "-1", if the array bb could not be obtained from any array aa;
• nn integers a1,a2,…,ana1,a2,…,an, otherwise.

If there are several arrays of aa, you can output any.

Example

input

Copy

4
3
2 3 7 12 2
4
9 1 7 1 6 5
5
18 2 2 3 2 9 2
3
2 6 9 2 1

output

Copy

2 3 7 
-1
2 2 2 3 9 
1 2 6 

事先让n=n+2

枚举x的位置，取剩下n-1个数的最值，看是否等于n-2个数的和即可，排序与前缀和处理，很水的D

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
 
typedef long long int  ll;
 
ll a[200000+10];
ll sum[200000+10];
 
 
int main()
{
 
     int t ;
 
     cin>>t ;
 
     while(t--)
     {
         int n;
 
         cin>>n;
 
         for(int i=1;i<=n+2;i++)
         {
             cin>>a[i];
         }
 
         sort(a+1,a+1+n+2);
 
         for(int i=1;i<=n+2;i++)
         {
             sum[i]=sum[i-1]+a[i];
 
         }
 
         int flag=0;
 
         int pos;
 
 
 
         n+=2;
 
         for(int i=1;i<=n;i++)
         {
             if(i!=n)
             {
 
                 ll l=sum[i-1];
 
                 ll r=sum[n-1]-sum[i];
 
                 if(l+r==a[n])
                 {
                     flag=1;
 
                     pos=i;
 
                     break;
                 }
             }
             else
             {
                 if(sum[n-2]==a[n-1])
                 {
                     flag=1;
 
                     pos=n;
 
 
                     break;
                 }
             }
         }
 
         if(flag==0)
         {
             cout<<-1<
         }
         else
         {
             if(pos==n)
             {
                 for(int i=1;i<=n-2;i++)
                 {
                     cout<" ";
                 }
 
                 cout<
             }
             else
             {
                 for(int i=1;i
                 {
                     cout<" ";
                 }
 
                 for(int i=pos+1;i
                 {
                     cout<" ";
                 }
 
                 cout<
             }
         }
     }
 
    return 0;
}