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<iostream>
#include<string>
#include<vector>
#include<string.h>
#include<set>
#include<algorithm>
#include<queue>
#include<map>
#include<stdio.h>
#include<math.h>
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<<endl;
         }
         else
         {
             if(pos==n)
             {
                 for(int i=1;i<=n-2;i++)
                 {
                     cout<<a[i]<<" ";
                 }

                 cout<<endl;
             }
             else
             {
                 for(int i=1;i<pos;i++)
                 {
                     cout<<a[i]<<" ";
                 }

                 for(int i=pos+1;i<n;i++)
                 {
                     cout<<a[i]<<" ";
                 }

                 cout<<endl;
             }
         }
     }

    return 0;
}