题目描述

Description

Anton goes to school, his favorite lessons are arraystudying. He usually solves all the tasks pretty fast, but this time the teacher gave him a complicated one: given two arrays b and c of length n, find array a, such that:

where a and b means bitwise AND, while a or b means bitwise OR.
Usually Anton is good in arraystudying, but this problem is too hard, so Anton asks you to help.
给你和，找到满足符合以下要求的：
有解输出,无解输出-1

Input

The first line of the input contains a single integers n (1 ≤ n ≤ 200 000) — the size of arrays b and c.

The second line contains n integers bi (0 ≤ bi ≤ 109) — elements of the array b.

Third line contains n integers ci (0 ≤ ci ≤ 109) — elements of the array c.

Output

If there is no solution, print  - 1.
Otherwise, the only line of the output should contain n non-negative integers ai — elements of the array a. If there are multiple possible solutions, you may print any of them.

input

4
6 8 4 4
16 22 10 10

output

3 5 1 1 

input

5
8 25 14 7 16
19 6 9 4 25

output

-1

题目分析

前置技能
证明如下：
我们按位讨论 每一位可以分为4种情况





于是我们把和加和，得到
令

所以，可以在内拿出，并且有且只有一个解。
但是是与相关联的 我们还要检验，是否成立
我们预处理出所有的每一位的个数，对于每个 我们来拆位计算对应的，
设现在枚举到第位
如果，对的贡献是，对的贡献是。
否则，对的贡献是，对的贡献是。
所以：


可以在时间内计算出，，之后一下就好了

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
long long read()
{
    long long sum=0;
    char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') sum=sum*10+(c-'0'),c=getchar();
    return sum;
}
int t,n;
long long a[200005],b[200005],c[200005],sum[200005];
int bits[50];
void work()
{
    scanf("%d",&n);
    memset(sum,0,sizeof sum);
    memset(bits,0,sizeof bits);
    for(int i=1;i<=n;i++) b[i]=read();
    for(int i=1;i<=n;i++) c[i]=read(),sum[i]=b[i]+c[i],sum[0]+=sum[i];
    sum[0]/=2*n;
    for(int i=1;i<=n;i++) a[i]=(sum[i]-sum[0])/n;
    for(int i=1;i<=n;i++)
      for(int j=0;j<31;j++) bits[j]+=( a[i]&(1ll<<j) )?1:0;
    int flag=1;
    for(int i=1;i<=n;i++)
    {
        long long bsum=0,csum=0;
        for(int j=0;j<31;j++)
        { 
            bsum=bsum+(long long)(((a[i]&(1ll<<j))?bits[j]:0)*(1ll<<j));
            csum=csum+(long long)(((a[i]&(1ll<<j))?n:bits[j])*(1ll<<j));
        }
        if(b[i]!=bsum||c[i]!=csum) { flag=0; break; }
    }
    if(flag) for(int i=1;i<=n;i++) printf("%lld%c",a[i],i==n?'\n':' ');
    else printf("-1\n");
}
int main()
{
    scanf("%d",&t);
    while(t--) work();
    return 0;
}